A regular connected graph has k loops?

Suppose $A$ is an order-$n$ matrix of zeroes and ones such that $A^2 = J$, the matrix of all ones. Show that $A$ has exactly $k$ ones along the diagonal, where $k^2 = n$.

I can show that $AJ=JA=kJ$, so in graph theoretic terms, $A$ is a regular graph of order $k$. And $A$ is connected, or else $A^2$ would have zeroes in it. I wonder if there's a theorem that can establish that the graph has exactly $k$ loops? Or perhaps it's more obvious from a matrix perspective.

I know that regularity and connectivity by itself isn't sufficient, since for example the matrix

$$A_\varnothing=\begin{bmatrix}1& & &1\\ &1&1& \\1& &1& \\&1&&1\end{bmatrix}$$

is $k$-regular and connected, but fails to satisfy $A_\varnothing^2 = J$ and fails to have $k$ ones along the diagonal.

An example that does exhibit this property is

$$A_\checkmark = \begin{bmatrix}1&1&&\\&&1&1\\1&1&&\\&&1&1\end{bmatrix}$$

• What if $n$ is not a square integer? – Aritro Pathak Nov 12 '17 at 21:16
• Then I think the condition $A^2 = J$ is impossible to satisfy. – user326210 Nov 12 '17 at 21:38
• The $ij$ entry of $A^{2}$ represents the number of walks of length 2 between vertices $v_{i}$ and $v_{j}$. Since you are not assuming that your matrix is symmetric, you are working with digraphs. What can you say about a vertex that does not have a loop? – Morgan Rodgers Nov 13 '17 at 1:41
• Yes, that's the correct interpretation. Vertices without loops have outgoing edges to $k$ distinct other vertices, and incoming edges from $k$ distinct other vertices. Exactly one vertex has both an outgoing and an incoming edge from it, so that there's exactly one path of length 2 from the vertex to itself. – user326210 Nov 13 '17 at 1:43
• Also, two vertices with loops cannot be adjacent. This should be able to force all the details. – Morgan Rodgers Nov 13 '17 at 1:54

I found I can prove it as a theorem using properties of eigenvalues(!).

The trick is that for a matrix of zeroes and ones, the number of ones along the diagonal is equal to the sum of the values along the diagonal (the trace of the matrix). But the trace of a matrix is also equal to the sum of its (generalized) eigenvalues. Hence it's enough to prove that $A$ has generalized eigenvalues $0$ (with multiplicity $n-1$) and $k$ (with multiplicity 1).

A nice aspect about this approach is that it generalizes to higher powers of $A$, and to matrices whose entries are not just zeroes and ones:

Let $r$ be a positive integer and let $A$ be any $n\times n$ matrix such that $A^r = J$. Then :

• Every row and column of $A$ sums to $k \equiv n^{1/r}$.
• The trace of $A$ is equal to $k$.

In detail:

1. We are given that $A^2 = J$.
2. From this we can show that $AJ = JA = kJ$ for some scalar value $k$. [See proof below.]
3. Looking at a single column of $AJ = kJ$, we find that the vector of ones is an eigenvector of $A$ with eigenvalue $k$.
4. Combining $A^2 = J$ and $AJ = kJ$, we obtain $A^3 = kA^2$. This allows us to rewrite all higher powers of $A$ in terms of $A^2$.
5. Using the rewrite rule $A^3 = kA^2$, we find that the generalized eigenvalues of $A$ are $k$ (with multiplicity 1) and 0 (with multiplicity $n-1$). [See proof below.]
6. The trace of a matrix is the sum of its generalized eigenvalues; hence the trace of $A$ is just $k+0+0+\ldots+0 = k$.
7. The trace of a matrix of zeroes and ones is equal to the number of ones along the diagonal. Hence there are exactly $k$ ones along the diagonal (exactly $k$ vertices with loops); QED.

Proof of (2): we note that the matrix $J$ 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.

If $A^2 = J$ by hypothesis, then $A^3 = AJ = JA$. But $AJ$ is the matrix of row sums of $A$, and $JA$ is the matrix of column sums of $A$. If they're equal, then every row and column of $A$ must have the same sum— call it $k$.

Consequently, $AJ = JA = kJ$ (the matrix where every entry is $k$.)

As a corollary, we can prove that $k^2 = n$ (the order of the matrix) because $J^2 = nJ$ (the row sums of $J$ are all $n$) and $J^2 = JA^2 = (JA)A = kJA = k(JA) = k(kJ) = k^2J$, so $nJ = k^2 J$, which means that $k^2 = n$.

Proof of (5): The generalized eigenvalue formula is $$(A - \lambda I)^n v = 0.$$

From (3), above, we know that $k$ is an eigenvalue and hence a generalized eigenvalue. If $n=1$, this must be the only eigenvalue and we're done. Otherwise, we'll show that 0 is another generalized eigenvalue and that it has multiplicity $n-1$. Because there are exactly $n$ generalized eigenvalues, we can conclude that 0 is the only other eigenvalue, and that $k$ has multiplicity 1.

Considering the eigenvalue $\lambda = 0$, the generalized eigenvalue equation reduces to $A^n = 0$. But because $A^2 = J$ implies that $A^3 = kA^2$, we can prove by induction that $A^{r+2} = k^r A^2$ for integer $r \geq 0$. Hence $A^n = k^{n-2} A^2 = k^{n-2} J$. (Note: $n>2$ because $n$ is a perfect square and we're considering only the case $n>1$.)

Hence generalized eigenvectors of $A$ with eigenvalue 0 are vectors $v$ such that $$k^{n-2} J v = 0$$ or, eliminating the positive constant $k^{n-2}$, just $$Jv = 0.$$

But $Jv$ returns a vector where each entry is the sum of the entries in $v$:

$$Jv = (\sum_i v_i)\begin{bmatrix}1\\1\\\vdots \\ 1\end{bmatrix}$$

so $J$ sends to zero just those vectors whose entries sum to zero. The set of all such zero-sum vectors is a subspace of dimension $n-1$, so we have shown that $0$ is a generalized eigenvalue of $A$ with algebraic multiplicity $n-1$.

Because $k$ is an eigenvalue of $A$ and there are exactly $n$ generalized eigenvalues, it follows that $k$ is the only other generalized eigenvalue and that it has multiplicity 1. Q.E.D.

• Do you mean to say that $k$ is the only nonzero eigenvalue? – Morgan Rodgers Nov 14 '17 at 15:34
• Yes, I said it in point (7) and I believe I've shown it's true. – user326210 Nov 14 '17 at 15:50
• But in the beginning you say that $A$ has exactly one eigenvalue; but in fact $A$ will have exactly 2 eigenvalues, $k$ and $0$. I see now that you say this correctly in point (7). – Morgan Rodgers Nov 14 '17 at 16:55
• This might be a stupid question, but by showing that eigenvectors with eigenvalue $k$ are all linearly dependent, how do you ensure that the multiplicity of $k$ in the characteristic polynomial is 11? You might well have the algebraic multiplicity of $k$ in the characteristic polynomial to be $≥2$ with all eigenvectors of the eigenvalue $k$ linearly dependent, right? (in which case A is not diagonalizable). – Aritro Pathak Nov 14 '17 at 21:57
• @AritroPathak. Oh that's a good question and I need to show that---I was thinking about geometric instead of algebraic multiplicity. The argument can go like this: because any polynomial with $P(A)=0$ must be a (polynomial) multiple of the characteristic polynomial, we know the algebraic multiplicity of $k$ can't be bigger than the exponent of $(\lambda - k)$ in $P$. With that, I think I don't need the Proof of part 7 --- right? – user326210 Nov 15 '17 at 5:14

You are unlikely to find a theorem that says this, you just have to argue combinatorially.

First, if $G$ is $k$-regular, and we have a vertex $v$ with a loop, then the number of vertices of $G$ is given by $1+(k-1)+(k-1)k) = k^{2}$ ($v$, vertices with an out-edge from $v$, vertices with an out-edge from one of the previous set; these are all distinct because otherwise there would be two paths). Therefore $n=k^{2}$.

Consider the vertices with loops; there can be no edges between these vertices because that would give two walks of length 2 between them (loop then edge, or edge then loop). So if we fix a vertex $v$ with a loop, then there are $(k-1)$ loop-free vertices in its out-set. Any other vertex $v^{\prime}$ with a loop must be at distance 2 from $v$, so there must be a $w$ in the out-set of $v$ with an out-edge to $v^{\prime}$. But there must be only one path of length 2 from $v$ to $v^{\prime}$ so $w$ is unique. This tells us there can be at most $k-1$ vertices distinct from $v$ with loops, giving a total of at most $k$ vertices with loops.

I'll leave it to you to show that equality actually holds.