Coprime matrix little puzzle

Damian · 2012-12-01, 22:56

Today I thought of this puzzle: to find a square matrix over the integers, such that each coeficient satisfices (at the same time)
(1) being coprime to any consecutive coeficient (to the left/right or up/down)
(2) being not coprime with any other coeficient.

It is easy to find examples of 2x2 matrices that satisfy (1) and (2), for example take any pair of prime numbers p and q, and you can have the matrix
$A = \begin{pmatrix} p & q \\ q & p \end{pmatrix}$

It is a little more difficult to find a 3x3 matrix that satisfies (1) and (2). I got up with

$A = \begin{pmatrix} 2432694 & 21772835 & 6906614 \\ 20764055 & 682 & 270605235 \\ 5122502 & 134419935 & 90706 \end{pmatrix}$

It's interesting (to me) that there are not many such matrices with "small" (in absolute number and in number of divisors) coeficients. Anyway there are infinite such matrices for any value of n.

Can you give another example?

science_man_88 · 2012-12-02, 02:57

$A = \begin{pmatrix} p & q & r\\ r & p & q\\ q & r & p\end{pmatrix}$ where r is a number that divides by p or q

for example:

$A = \begin{pmatrix} 2 & 3 & 4\\ 4 & 2 & 3\\ 3 & 4 & 2\end{pmatrix}$

this should work according to what I understand,

never mind I see my error now.

axn · 2012-12-02, 02:59

Does this work?
[10, 231, 26]
[273, 2, 165]
[22, 195, 14]

In general
[p.a, q.c.d, p.b]
[q.b.c, p, q.a.d]
[p.d, q.a.b, p.c]

Does this work?

Damian · 2012-12-02, 08:32

Hi Axn,
Yes, indeed you found a better example than mine.
I would search a 4x4 example, but this turned out to be rather boring, soo...

science_man_88 · 2012-12-02, 17:28

Quote:

Originally Posted by axn

Does this work?
[10, 231, 26]
[273, 2, 165]
[22, 195, 14]

In general
[p.a, q.c.d, p.b]
[q.b.c, p, q.a.d]
[p.d, q.a.b, p.c]

Does this work?

[a.b, c.e, a.d]
[c.d.g, a, b.c.f]
[a.e.f, b.c.d, a.e.g]

I get this as working as well, I worked it out on paper.

henryzz · 2012-12-02, 23:41

Quote:

Originally Posted by Damian

Hi Axn,
Yes, indeed you found a better example than mine.
I would search a 4x4 example, but this turned out to be rather boring, soo...

I wouldn't say boring. We haven't worked out the generalization to nxn matrices yet(or proven we have found all forms for 3x3(which I doubt)).

science_man_88 · 2012-12-03, 01:27

Quote:

Originally Posted by henryzz

I wouldn't say boring. We haven't worked out the generalization to nxn matrices yet(or proven we have found all forms for 3x3(which I doubt)).

good thing you doubt, because I started at a different square this time and got:

[bd acgf be]
[cef b cdg]
[bg cde bf]

though I'm not sure I suspect there's three type of squares to start from in a 3 by 3, my original started from the top left corner,this one is from the top center, I suspect the other main form is from the center, I may try that next, also I'm not sure if a change in method will produce a different one.

edit: and the center produced ( for me at least):

[cdf bg ceh]
[be ac bd]
[cdg bfh ceg]

science_man_88 · 2012-12-03, 13:50

I think I can show that infinite forms of 3 by 3 exist:

[bd acgf be]
[cef b cdg]
[bg cde bf]

this is already balanced, add a varible anywhere and make the rest not coprime ( they already are so add the variable anywhere that makes them not touch):

[bd acgf be]
[cef bh cdg]
[bg cde bf]

works, so does:

[bdh acgf beh]
[cef bh cdg]
[bgh cde bfh]

etc.

my basic ones seem to show a pattern of a perimeter of 21 letters axn's appears to break that mold as can the additions I showed. I have other possible patterns in the basic ones I came with that can all be broken as well.

henryzz · 2012-12-04, 14:31

Quote:

Originally Posted by science_man_88

[bd acgf be]
[cef bh cdg]
[bg cde bf]

This doesn't work according to rule 2. The corners are coprime with h.
I reckon there are a finite number of solutions with the least possible number of letters.

science_man_88 · 2012-12-04, 14:34

Quote:

Originally Posted by henryzz

This doesn't work according to rule 2. The corners are coprime with h.
I reckon there are a finite number of solutions with the least possible number of letters.

all the must not be coprime rule states is they have 1 factor in common which they do.

henryzz · 2012-12-04, 17:10

Quote:

Originally Posted by science_man_88

all the must not be coprime rule states is they have 1 factor in common which they do.

Didn't notice the b.

It looks like axn posted a 6 variable solution in #3.
All of science_man's seem to be 7 or 8 variables.

Are there any more 6s?
Can anyone prove 6 is is the minimal number?
What is the minimal number for 4x4?

2012-12-01, 22:56	#1
Damian May 2005 Argentina 2·3·31 Posts	Coprime matrix little puzzle Today I thought of this puzzle: to find a square matrix over the integers, such that each coeficient satisfices (at the same time) (1) being coprime to any consecutive coeficient (to the left/right or up/down) (2) being not coprime with any other coeficient. It is easy to find examples of 2x2 matrices that satisfy (1) and (2), for example take any pair of prime numbers p and q, and you can have the matrix $A = \begin{pmatrix} p & q \\ q & p \end{pmatrix}$ It is a little more difficult to find a 3x3 matrix that satisfies (1) and (2). I got up with $A = \begin{pmatrix} 2432694 & 21772835 & 6906614 \\ 20764055 & 682 & 270605235 \\ 5122502 & 134419935 & 90706 \end{pmatrix}$ It's interesting (to me) that there are not many such matrices with "small" (in absolute number and in number of divisors) coeficients. Anyway there are infinite such matrices for any value of n. Can you give another example? Last fiddled with by Damian on 2012-12-01 at 22:58

2012-12-02, 02:57	#2
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶×131 Posts	$A = \begin{pmatrix} p & q & r\\ r & p & q\\ q & r & p\end{pmatrix}$ where r is a number that divides by p or q for example: $A = \begin{pmatrix} 2 & 3 & 4\\ 4 & 2 & 3\\ 3 & 4 & 2\end{pmatrix}$ this should work according to what I understand, never mind I see my error now. Last fiddled with by science_man_88 on 2012-12-02 at 03:00

2012-12-03, 13:50	#8
science_man_88 "Forget I exist" Jul 2009 Dumbassville 20C0₁₆ Posts	I think I can show that infinite forms of 3 by 3 exist: [bd acgf be] [cef b cdg] [bg cde bf] this is already balanced, add a varible anywhere and make the rest not coprime ( they already are so add the variable anywhere that makes them not touch): [bd acgf be] [cef bh cdg] [bg cde bf] works, so does: [bdh acgf beh] [cef bh cdg] [bgh cde bfh] etc. my basic ones seem to show a pattern of a perimeter of 21 letters axn's appears to break that mold as can the additions I showed. I have other possible patterns in the basic ones I came with that can all be broken as well. Last fiddled with by science_man_88 on 2012-12-03 at 13:57

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Consecutive numbers not coprime to Euler's totient...	carpetpool	Miscellaneous Math	5	2017-03-09 05:45
Connectivity Matrix	Xyzzy	Lounge	13	2017-02-21 18:29
12+256 matrix job	fivemack	Factoring	11	2009-08-18 17:39
GF(2) Matrix request	oslik	Factoring	22	2008-11-02 12:53
[Need help] about Matrix Polynomial	buan	Homework Help	3	2007-07-17 15:07

2012-12-02, 02:59	#3
axn Jun 2003 2²×5²×7² Posts	Does this work? [10, 231, 26] [273, 2, 165] [22, 195, 14] In general [p.a, q.c.d, p.b] [q.b.c, p, q.a.d] [p.d, q.a.b, p.c] Does this work?

2012-12-02, 08:32	#4
Damian May 2005 Argentina BA₁₆ Posts	Hi Axn, Yes, indeed you found a better example than mine. I would search a 4x4 example, but this turned out to be rather boring, soo...