[seqfan] Re: Number of nXn (0,1)-matrices A with A^2 = J?
Neil Sloane
njasloane at gmail.com
Fri Mar 10 00:35:46 CET 2017
and this later paper may be helpful:
Curtis, Frank, et al. "Central groupoids, central digraphs, and
zero-one matrices A satisfying A2= J." Journal of Combinatorial
Theory, Series A 105.1 (2004): 35-50.
I am tied up for the next few days, so if someone wants to
follow this path please do so!
Best regards
Neil
Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com
On Thu, Mar 9, 2017 at 6:28 PM, Neil Sloane <njasloane at gmail.com> wrote:
> In fact Benoit's approach and the approach via Universal Algebra
> may not be all that different. It may be that the Universal Algebra
> approach gives an algebraic way of describing Benoit's idea of
> subdividing the matrices into blocks.
> Best regards
> Neil
>
> Neil J. A. Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
>
> On Thu, Mar 9, 2017 at 6:12 PM, Neil Sloane <njasloane at gmail.com> wrote:
>> Well, if this is going to turn out to be a hard problem (although the
>> case c=3, matrices of size 9X9, should be doable), here is an
>> alternative
>> approach: according to the Ryser article I mentioned,
>> Don Knuth tackled this problem with the help of a computer around 1970,
>> in the context of universal algebras. He wrote two papers,
>> which I only glanced at (JCT 8 (1970), 376-390; and a paper in the
>> Leech (ed.) book, Computational Problem in Abstract Algebra). I did
>> not see any tables. I would happy to send copies to anyone who would
>> like to try to understand them.
>> Best regards
>> Neil
>>
>> Neil J. A. Sloane, President, OEIS Foundation.
>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>> Phone: 732 828 6098; home page: http://NeilSloane.com
>> Email: njasloane at gmail.com
>>
>>
>>
>> On Thu, Mar 9, 2017 at 5:40 PM, BenoĆ®t Jubin <benoit.jubin at gmail.com> wrote:
>>> Here is a method to construct some solutions A of size (n^2, n^2) with
>>> entries 0, 1 (integers, NOT modulo 2), of the equation A^2 = J.
>>>
>>> Decompose A into n^2 blocks of size (n, n). Each block can be any
>>> matrix with 1's in a given row and 0's elsewhere. One has to be
>>> careful to not use twice the same block in a row of blocks. This
>>> gives, it seems, (n!)^n solutions. The transposed matrices give (n!)^n
>>> other solutions.
>>>
>>> There are probably many other solutions, choosing special blocks (in
>>> the case of matrices of size (2^2, 2^2)-matrices, the blocks can be
>>> the identity and the "antidiagonal", as found by Edwin Clark).
>>>
>>> I hope this helps.
>>>
>>> Regards,
>>> Benoit
>>>
>>>
>>>
>>>
>>> On Sat, Mar 4, 2017 at 8:31 PM, W. Edwin Clark <wclark at mail.usf.edu> wrote:
>>>> I get the following 12 4x4 0,1 matrices A with A^2 = J.
>>>>
>>>> 1 1 0 0
>>>> 0 0 1 1
>>>> 1 1 0 0
>>>> 0 0 1 1
>>>>
>>>> 1 1 0 0
>>>> 0 0 1 1
>>>> 0 0 1 1
>>>> 1 1 0 0
>>>>
>>>> 0 0 1 1
>>>> 1 1 0 0
>>>> 1 1 0 0
>>>> 0 0 1 1
>>>>
>>>> 0 0 1 1
>>>> 1 1 0 0
>>>> 0 0 1 1
>>>> 1 1 0 0
>>>>
>>>> 1 0 1 0
>>>> 1 0 1 0
>>>> 0 1 0 1
>>>> 0 1 0 1
>>>>
>>>> 1 0 1 0
>>>> 0 1 0 1
>>>> 0 1 0 1
>>>> 1 0 1 0
>>>>
>>>> 0 1 0 1
>>>> 1 0 1 0
>>>> 1 0 1 0
>>>> 0 1 0 1
>>>>
>>>> 0 1 0 1
>>>> 0 1 0 1
>>>> 1 0 1 0
>>>> 1 0 1 0
>>>>
>>>> 0 1 1 0
>>>> 0 1 1 0
>>>> 1 0 0 1
>>>> 1 0 0 1
>>>>
>>>> 0 1 1 0
>>>> 1 0 0 1
>>>> 0 1 1 0
>>>> 1 0 0 1
>>>>
>>>> 1 0 0 1
>>>> 0 1 1 0
>>>> 1 0 0 1
>>>> 0 1 1 0
>>>>
>>>> 1 0 0 1
>>>> 1 0 0 1
>>>> 0 1 1 0
>>>> 0 1 1 0
>>>>
>>>>
>>>> On Sat, Mar 4, 2017 at 11:38 AM, Neil Sloane <njasloane at gmail.com> wrote:
>>>>
>>>>> Joerg, you are right. I should have stuck with
>>>>> my ugly solutions, which were
>>>>> 1010
>>>>> 1010
>>>>> 0101
>>>>> 0101
>>>>> and
>>>>> 0101
>>>>> 0101
>>>>> 1010
>>>>> 1010
>>>>> Are there any other 4X4 0,1 matrices with A^2 = J = "all-ones" ?
>>>>> Best regards
>>>>> Neil
>>>>>
>>>>> Neil J. A. Sloane, President, OEIS Foundation.
>>>>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>>>>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>>>>> Phone: 732 828 6098; home page: http://NeilSloane.com
>>>>> Email: njasloane at gmail.com
>>>>>
>>>>>
>>>>>
>>>>> On Sat, Mar 4, 2017 at 3:17 AM, Joerg Arndt <arndt at jjj.de> wrote:
>>>>> > * Neil Sloane <njasloane at gmail.com> [Mar 04. 2017 09:00]:
>>>>> >> I just came across an old paper of Herb Ryser (A generalization
>>>>> >> of the matrix equation A^2=J, Linear Alg. Applic., 3 (1970),451-460)
>>>>> >> where he mentions in passing the unsolved problem of finding
>>>>> >> the number of n X n real (0,1) matrices A such that A^2 is the
>>>>> >> all-ones matrix J.
>>>>> >>
>>>>> >> He says that A must have constant row and column sums c, and c^2 = n.
>>>>> >> Also trace A = c. So n must be a square, n=c^2.
>>>>> >>
>>>>> >> There is a long entry in the Index to the OEIS under
>>>>> >> matrices, binary
>>>>> >> but this problem doesn't seem to be mentioned there.
>>>>> >> Is this sequence in the OEIS? (If so, it should
>>>>> >> be mentioned in the index entry.)
>>>>> >> I'm pretty sure I've seen the problem before, but a quick
>>>>> >> search in the OEIS didn't find it. Let n = c^2. Then there is one
>>>>> >> solution if c=1, and if someone could work out the answers for c=2 and
>>>>> >> maybe 3, that might be enough to locate it.
>>>>> >>
>>>>> >> Here is one solution for c=2:
>>>>> >> 1010
>>>>> >> 0101
>>>>> >> 1010
>>>>> >> 0101
>>>>> >
>>>>> > This one has trace = c^2 = 4, not c as stated above.
>>>>> >
>>>>> >> and permuting the rows is allowed - so is the answer 6 if c=2?
>>>>> >>
>>>>> >> Neil
>>>>> >>
>>>>> >> --
>>>>> >> Seqfan Mailing list - http://list.seqfan.eu/
>>>>> >
>>>>> > --
>>>>> > Seqfan Mailing list - http://list.seqfan.eu/
>>>>>
>>>>> --
>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>>
>>>>
>>>> --
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list