mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2012-12-01, 22:56   #1
Damian
 
Damian's Avatar
 
May 2005
Argentina

2·3·31 Posts
Default 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
Damian is offline   Reply With Quote
Old 2012-12-02, 02:57   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2012-12-02, 02:59   #3
axn
 
axn's Avatar
 
Jun 2003

22×3×409 Posts
Default

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?
axn is offline   Reply With Quote
Old 2012-12-02, 08:32   #4
Damian
 
Damian's Avatar
 
May 2005
Argentina

2×3×31 Posts
Default

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...
Damian is offline   Reply With Quote
Old 2012-12-02, 17:28   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by axn View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-12-02, 23:41   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

133408 Posts
Default

Quote:
Originally Posted by Damian View Post
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)).
henryzz is offline   Reply With Quote
Old 2012-12-03, 01:27   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-12-03, 13:50   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2012-12-04, 14:31   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

25×3×61 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2012-12-04, 14:34   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-12-04, 17:10   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

25·3·61 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
henryzz is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 00:16.

Thu Apr 15 00:16:43 UTC 2021 up 6 days, 18:57, 0 users, load averages: 1.67, 1.79, 1.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.