$A$ has all line sums equal to a positive number $k$ Let $A$ be a $(0,1)$ matrix of order $n$ that satisfies the matrix equation $A^2 = J$, where $J$ is the matrix of ones of order $n$. Show that $A$ has all line sums equal to a positive number $k$ and that $n = k^2$. Moreover $A$ must have exactly $k$ ones on its main diagonal.
Sum of elements in one row or column is called line sums.
 A: The trick is to note that matrix multiplication by $J$ actually computes the column/row sums of a matrix.


*

*For any order-$n$ matrix $M$, let $r_1, \ldots, r_n$ be its row sums. Note that by matrix multiplication rules, $MJ$ is the matrix of row sums:
$$MJ = \begin{bmatrix}r_1 & r_1 & \ldots & r_1\\r_2 & r_2 & \ldots & r_2\\\vdots & \vdots & &\vdots\\ r_n & r_n & \ldots & r_n\\\end{bmatrix}$$
and similarly $JM$ is the matrix of column sums.

*We know that $A^2 = J$. Hence: 


*

*$A^3 = AJ = JA$, when we multiply by $A$.

*But $AJ$ computes the row sums of $A$, and $JA$ computes the column sums. If they're equal, it means that each row and column of $A$ adds up to the same number— call it $k$. (The sum $k$ must be positive because $A$ consists of zeroes and ones, and $A$ is not the zero matrix.)

*Hence we can write $AJ = JA = kJ$ (the matrix where each entry is $k$.)


*We can show that $J^2 = nJ$, because the sum of every row/column of $J$ is just $n$. But because $AJ = kJ$, we also know that:


*

*$J^2 = A^2 J = AAJ = A(AJ) = A(kJ) = k(AJ) = k(kJ) = k^2 J$

*Hence $J^2 = nJ$ and also $J^2 = k^2 J$

*In other words, $k^2 = n$.


*We can show that there are exactly $k$ ones along the diagonal, using some facts about eigenvalues (I'm not sure if there's a simpler way.)


*

*If $A$ consists of zeroes and ones, then the number of ones along the diagonal is equal to the sum of the values along the diagonal. This is the trace of matrix $A$. Hence we need to show that the trace of $A$ is equal to $k$.  The trace of a matrix is also equal to the sum of its (generalized) eigenvalues, so it suffices to show that $A$ has exactly one nonzero eigenvalue, namely $k$.

*We already know that $AJ = kJ$. Looking at a single column, it follows that the vector $\vec{u}$ of all ones is an eigenvector of $A$ with eigenvalue $k$.

*Combining $AJ = kJ$ with $A^2 = J$, we find that $A^3 = kA^2$.

*A generalized eigenvector $v$ is a vector that makes $(A-\lambda I)^n v = 0$. When $\lambda$ is zero, this equation becomes $A^n v = 0$. Because $A^3 = kA^2$, we can show that this condition is equivalent to $A^2 v = 0$.

*Hence $v$ is a generalized eigenvector of $A$ with eigenvalue zero just if $A^2v = Jv = 0$. Because $Jv$ returns a vector where every entry is the sum of all the entries in $v$, $Jv$ is zero just if the entries in $v$ sum to zero.

*The set of all zero-sum vectors is a space of dimension $n-1$. (It's the space of all vectors perpendicular to $[1,1,\ldots,1]$.) Hence 0 is a generalied eigenvalue of $A$, and its multiplicity is $n-1$.

*But an order-$n$ matrix has exactly $n$ generalized eigenvalues— hence $k$ is one of them, and $0$ (counting multiplicities) is the rest of them.

*It follows that the trace of $A$ is equal to $k+0+0+\ldots+0 = k$, which proves that $A$ has exactly $k$ ones along the diagonal.




As an aside, none of these results really depend on $A$ being a matrix of zeroes and ones. Adapting the same proof technique we used here, we can prove the more general result:

Let $r\geq 1$ be an integer and let $M$ be any degree-$n$ matrix with $M^r = J$. Then 
  
  
*
  
*The entries in each row and each column of $M$ add up to $k\equiv n^{1/r}$.
  
*The trace of $M$ is equal to $k$.
  
*If $M$ consists of zeroes and ones, then $M$ has exactly $k$ ones along the diagonal.
  


If you want a concrete construction of matrices $A$ with the above property: define the matrix $M[k,r,a]$ to be an order $k^r$ matrix with
$$M[k, r, a]_{i,j} = [1\text{ if }(0 \leq ik^a+j < k^a)\pmod {k^r};\; 0 \text{ otherwise } ]$$
This complicated formula is better explained by visual example:
$$M[k=2; r=3; a=1] = \begin{bmatrix}
1 & 1 & &&&&&\\
&&1 & 1 & &&&\\
&&&&1 & 1 & &\\
&&&&&&1 & 1 \\
1 & 1 & &&&&&\\
&&1 & 1 & &&&\\
&&&&1 & 1 & &\\
&&&&&&1 & 1 \\
\end{bmatrix}$$
where the length of the runs is determined by $k^a$, and the size of the matrix is determined by $k^r$.
Then I claim without proof that that $A \equiv M[k,r,1]$ is an order-$k^r$ matrix with $A^r = J$. 
More generally, I expect $M[k, r, a] \cdot M[k,r,b] = M[k,r,a+b]$. (In particular, $M[k,r,0]$ is the order-$k^r$ identity matrix.)
