[seqfan] Re: Number of nXn (0,1)-matrices A with A^2 = J?

Benoît Jubin benoit.jubin at gmail.com
Thu Mar 9 23:40:55 CET 2017


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/



More information about the SeqFan mailing list