Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

closed as not a real question by Ross Millikan, Bill Cook, Pedro Tamaroff, t.b., Gerry Myerson Jul 2 '12 at 6:30

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
Please don't use caps lock. –  Norbert Jun 24 '12 at 21:54
1  
Please don’t use all-caps: it comes across as SHOUTING, and it’s hard to read besides. –  Brian M. Scott Jun 24 '12 at 21:55
6  
Beside CapsLock, what is your question, exactly?... –  Patrick Da Silva Jun 24 '12 at 21:56
add comment

3 Answers 3

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

share|improve this answer
    
Wouldn't the duality of points and lines suggest you can get a symmetric matrix out of any finite projective plane? –  Gerry Myerson Jun 25 '12 at 1:46
    
@Gerry, I'm not sure. In the bipartite graph model, I'm not sure there is an ordering of the second thirteen points that makes the bipartite graph show a reflection symmetry. So far, I have not found anything conclusive. –  Will Jagy Jun 25 '12 at 1:52
    
@Gerry, I found the 13 by 13 example as $P P^T$ with $P$ "binary" but not symmetric. I tried hard enough to doubt the possibility of $P$ symmetric. No proof. $P$ found by hand. Checked with gp-pari. –  Will Jagy Jun 25 '12 at 2:46
1  
Let $V$ be the 3-dimensional vector space over the field of $q$ elements. The points of a projective plane are the 1-dimensional subspaces of $V$, the lines are the 2-dimensional subspaces. I think each 1-d subspace $L$ has a unique 2-d orthogonal complement $L^{\perp}$, and that $L^{\perp}$ contains $M$ if and only if $M^{\perp}$ contains $L$. If that's right, it tells you how to make a symmetric incidence matrix. Mind you, it's not clear this has anything to do with what OP wants. –  Gerry Myerson Jun 25 '12 at 5:16
1  
Rows: 0000000001111, 0010001010100, 0100010100100, 0000100111000, 0001011001000, 0010110000001, 0100101000010, 0011000100010, 0101000010001, 1001100000100, 1110000001000, 1000001100001, 1000010010010. –  Gerry Myerson Jun 25 '12 at 7:03
show 2 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.