0
$\begingroup$

I am working with the square-roots of square symmetric matrices. The answers are to be binary symmetric matrices.

If we take the matrix $M = \begin{pmatrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\1&0&0&0&0&1&1\\0&1&0&0&1&0&1\\0&1&0&1&0&1&0\\0&0&1&0&1&1&0\\0&0&1&1&0&0&1 \end{pmatrix},$ then $M^2$ will yield a $7 \times 7$ matrix with $3$ down the main diagonal and $1$ elsewhere.Once we have the matrix $M^2$ then we want to take the square root of it in order to get M.Now this is the simplest of all examples that I can give. M is the incidence matrix of a symmetric balanced incomplete block design. This design has 7 varieties, 7 blocks,each variety occurs in 3 blocks,each block contains 3 varieties, each pair of varieties occurs in exactly one block. If you are familiar with block designs then the parameters are (v,b,r,k,l)=(7,7,3,3,1) known as the fano plane.

  • 6
    Beside CapsLock, what is your question, exactly?...2012-06-24

3 Answers 3

4

I believe what you have found is what happens when you take the Fano plane, that is a finite projective plane of "order" 2, and write it as a bipartite graph on 7 plus 7 vertices. I think it is an artifact of small dimension that you are able to have your "binary" matrix also be symmetric. There is a projective plane of order 3, see FANO.
I think you can begin with a 13 by 13 symmetric matrix with 4's on the main diagonal and 1's elsewhere, and write it as $P P^T$ where $P$ is "binary" but not necessarily symmetric. I will see if I can construct such a $P$ myself. Meanwhile, it would appear to be impossible to do this with the 43 by 43 matrix with 6's on the main diagonal and 1's elsewhere.

The reason that it is impossible to do this with a 43 by 43 matrix with 7's rather than 6's on the main diagonal and 1's elsewhere is that the design (43,43,7,7,1) does not exist. This design is known as a symmetric balanced incomplete block design.

EDIT: if we take $ P \; = \; \left( \begin{array}{ccccccccccccc} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \end{array} \right), $ then $P \; P^T$ is the 13 by 13 matrix with 4 on the main diagonal and 1 elsewhere. I do not see how to do this with symmetric $P.$ Proof of impossibility would be another matter.

EDITEDIT: Note that $P^T \; P = P \; P^T.$

  • 1
    Rows: 0000000001111, 0010001010100, 0100010100100, 0000100111000, 0001011001000, 0010110000001, 0100101000010, 0011000100010, 0101000010001, 1001100000100, 1110000001000, 1000001100001, 1000010010010.2012-06-25
2

Gerry Myerson gave a recipe for finding a symmetric solution, also providing a solution in a comment. I wanted to implement that while preserving the structure of the Don Giles matrix for order 2 (Fano plane). That is, I wanted the first four rows and first four columns to be the analogous pattern to the 7 by 7. Gerry's method amounts to this: take all 13 lines in $\mathbb F_3^3,$ where $\mathbb F_3$ is the field with three elements. The 13 lines can be parametrized by triples of $1,0,-1,$ where the first nonzero entry is $+1.$ There is a $1$ in the matrix for a pair of vectors out of the 13 if their dot product is $0 \pmod 3.$ I decided to label the 13 points using capital letters. Notice that $A \cdot A \equiv G \cdot G \equiv J \cdot J \equiv M \cdot M \equiv 0 \pmod 3.$

LABELS: $ \begin{array}{rrrr} 0 & 0 & 1 & K \\ 0 & 1 & -1 & B \\ 0 & 1 & 0 & H \\ 0 & 1 & 1 & F \\ 1 & -1 & -1 & G \\ 1 & -1 & 0 & D \\ 1 & -1 & 1 & J \\ 1 & 0 & -1 & C \\ 1 & 0 & 0 & E \\ 1 & 0 & 1 & I \\ 1 & 1 & -1 & M \\ 1 & 1 & 0 & L \\ 1 & 1 & 1 & A \end{array} $

The order of both the rows and the columns of the matrix is alphabetical, $ABCDEFGHIJKLM.$ As I said, there is a $1$ in row $X,$ column $Y$ (and the reverse) when $X \cdot Y \equiv 0 \pmod 3.$

MATRIX: $ P \; = \; \left( \begin{array}{cccc|ccc|ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ \hline 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{array} \right). $

The result is that $P$ is symmetric and $P^2$ is the matrix with all 4's on the main diagonal and 1's everywhere else.

1

Had to screw around with the field of four elements. Not that bad. The pattern is different, there are the expected five null vectors, but the vector $(1,1,1)$ is orthogonal to all five, so I put that one first. The result is a symmetric matrix $P,$ such that $P^2$ is a 21 by 21 matrix with 5's on the main diagonal and 1's elsewhere.

$ P \; = \; \left( \begin{array}{c|cccc|cccc|cccc|cccc|cccc} 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{array} \right). $