mersenneforum.org Coprime matrix little puzzle
 Register FAQ Search Today's Posts Mark Forums Read

 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 26×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-02, 02:59 #3 axn     Jun 2003 22×52×72 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 BA16 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...
2012-12-02, 17:28   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

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.

2012-12-02, 23:41   #6
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

3×1,951 Posts

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)).

2012-12-03, 01:27   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

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]

Last fiddled with by science_man_88 on 2012-12-03 at 01:47

 2012-12-03, 13:50 #8 science_man_88     "Forget I exist" Jul 2009 Dumbassville 20C016 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
2012-12-04, 14:31   #9
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

16DD16 Posts

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.

2012-12-04, 14:34   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

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.

2012-12-04, 17:10   #11
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

3·1,951 Posts

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?

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 5 2017-03-09 05:45 Xyzzy Lounge 13 2017-02-21 18:29 fivemack Factoring 11 2009-08-18 17:39 oslik Factoring 22 2008-11-02 12:53 buan Homework Help 3 2007-07-17 15:07

All times are UTC. The time now is 10:58.

Sun Apr 11 10:58:04 UTC 2021 up 3 days, 5:38, 1 user, load averages: 1.21, 1.43, 1.65