[proofplan] The proof extracts the spectrum of a strongly regular graph from the matrix identity $A^2 + (b-a)A + (b-k)I = bJ$, derived by counting walks of length two. The Perron eigenvalue $k$ has multiplicity $1$ (by connectedness and $k$-regularity); every other eigenvector is orthogonal to $\mathbf{1}$ and therefore annihilated by $J$, reducing the identity to a quadratic $\lambda^2 + (b-a)\lambda + (b-k) = 0$ whose two roots $\lambda_\pm$ are the remaining eigenvalues. Let $s$, $t$ denote their multiplicities; the two linear conditions $s + t = n - 1$ and $\operatorname{tr}(A) = k + s\lambda_+ + t\lambda_- = 0$ determine $s$ and $t$. Since multiplicities are non-negative integers, the resulting closed-form expressions must be integers, giving the stated integrality constraint. [/proofplan] [step:Set up the adjacency structure and count walks of length two] Let $A = A_G \in \mathbb{R}^{n \times n}$ be the adjacency matrix of $G$, let $I$ be the $n \times n$ identity matrix, and let $J \in \mathbb{R}^{n \times n}$ be the all-ones matrix. Since $G$ is $(k, a, b)$-[strongly regular](/page/Strongly%20Regular%20Graph), for any two vertices $x, y \in V(G)$ the entry $(A^2)_{xy}$ counts the number of walks of length $2$ from $x$ to $y$, which equals the number of common neighbours of $x$ and $y$. We enumerate by cases: \begin{align*} (A^2)_{xy} = \begin{cases} k & \text{if } x = y, \\ a & \text{if } x \neq y \text{ and } x \sim y, \\ b & \text{if } x \neq y \text{ and } x \not\sim y. \end{cases} \end{align*} The case $x = y$ uses $k$-regularity: a walk of length $2$ from $x$ to $x$ chooses a neighbour of $x$ and returns, and there are exactly $\deg(x) = k$ such neighbours. The other two cases are the defining conditions of $(k,a,b)$-strong regularity. [guided] Before writing a matrix identity, we need to know what $A^2$ looks like entry by entry. Recall that for any adjacency matrix, the entry $(A^m)_{xy}$ counts walks of length $m$ from $x$ to $y$; here $m = 2$, so $(A^2)_{xy}$ is the number of common neighbours of $x$ and $y$. Now we use the hypotheses. The graph is $(k, a, b)$-strongly regular, meaning: - $G$ is $k$-regular, so every vertex has exactly $k$ neighbours, - every pair of adjacent vertices has exactly $a$ common neighbours, - every pair of non-adjacent distinct vertices has exactly $b$ common neighbours. For the diagonal: a walk of length $2$ from $x$ to $x$ passes through a neighbour of $x$ and returns, so $(A^2)_{xx} = \deg(x) = k$ by $k$-regularity. For the off-diagonal case $x \neq y$: if $x \sim y$ the common-neighbour count is $a$; if $x \not\sim y$ it is $b$. Thus \begin{align*} (A^2)_{xy} = \begin{cases} k & \text{if } x = y, \\ a & \text{if } x \neq y \text{ and } x \sim y, \\ b & \text{if } x \neq y \text{ and } x \not\sim y. \end{cases} \end{align*} [/guided] [/step] [step:Package the case analysis as a matrix identity $A^2 + (b-a)A + (b-k)I = bJ$] We assemble the three cases into a single matrix equation. Observe that: - $A$ has entry $1$ when $x \sim y$ (and hence $x \neq y$) and $0$ otherwise, - $I$ has entry $1$ when $x = y$ and $0$ otherwise, - $J - I - A$ has entry $1$ when $x \neq y$ and $x \not\sim y$, and $0$ otherwise. These three matrices form a partition of unity on $V(G) \times V(G)$: each pair $(x,y)$ is picked out by exactly one of them. Multiplying by the values from the case analysis, \begin{align*} A^2 = aA + b(J - I - A) + kI. \end{align*} Expanding and collecting terms, \begin{align*} A^2 + (b - a)A + (b - k)I = bJ. \tag{$\star$} \end{align*} [guided] We just derived the entry-by-entry formula for $A^2$. The next move is to rewrite this as a matrix equation, because then we can feed it to an arbitrary eigenvector and extract spectral information. The strategy is to express $A^2$ as a linear combination of matrices whose entry patterns match the three cases. The natural basis is: - $A$: entry $1$ iff $x \sim y$ (note $A_{xx} = 0$), - $I$: entry $1$ iff $x = y$, - $J - I - A$: entry $1$ iff $x \neq y$ and $x \not\sim y$. These three matrices partition $V(G) \times V(G)$: for any pair $(x,y)$, exactly one of "same vertex", "adjacent pair", "non-adjacent distinct pair" holds, and exactly one of $I, A, J - I - A$ has a $1$ there. So \begin{align*} A^2 = k \cdot I + a \cdot A + b \cdot (J - I - A). \end{align*} Rearranging so only scalars and the matrices $A^2, A, I, J$ appear: \begin{align*} A^2 + (b - a)A + (b - k)I = bJ. \tag{$\star$} \end{align*} This is the key identity. It looks like a quadratic in $A$ — the right-hand side $bJ$ is the obstruction preventing $A$ from literally satisfying a quadratic polynomial. We will show that $J$ acts as zero on the orthogonal complement of $\mathbf{1}$, which is where $\lambda \neq k$ eigenvectors live, so on that subspace the identity collapses to a true quadratic. [/guided] [/step] [step:Identify the Perron eigenvalue $k$ as a simple eigenvalue with eigenvector $\mathbf{1}$] Let $\mathbf{1} = (1, \ldots, 1)^\top \in \mathbb{R}^n$. Since $G$ is $k$-regular, $(A \mathbf{1})_i = \sum_{j \sim i} 1 = \deg(i) = k$ for every $i$, so $A \mathbf{1} = k \mathbf{1}$. A $(k,a,b)$-strongly regular graph with $0 < b \leq k$ is connected. By the [Eigenvalue Bounds via Degree](/theorems/2064) (Part (ii)), if $G$ is connected and $k$-regular then $k$ is an eigenvalue of $A$ with multiplicity exactly $1$ and eigenvector $\mathbf{1}$ (up to scalar). [guided] We want to separate the spectrum of $A$ into "the $\mathbf{1}$-direction" and "everything else". The $\mathbf{1}$-direction is easy: $k$-regularity means every row of $A$ sums to $k$, so $A \mathbf{1} = k \mathbf{1}$. Why is this eigenspace one-dimensional? This is exactly [Eigenvalue Bounds via Degree](/theorems/2064) (Part (ii)), which says: for a connected $k$-regular graph, the eigenvalue $k = \Delta(G)$ has multiplicity $1$ with eigenvector $\mathbf{1}$. We need to verify both hypotheses: 1. $G$ is $k$-regular — this is part of the $(k,a,b)$-strongly regular hypothesis. 2. $G$ is connected — a $(k,a,b)$-strongly regular graph with $b \geq 1$ is connected, since any two vertices are either adjacent or share a common neighbour, hence at distance $\leq 2$. (The degenerate case $b = 0$ corresponds to disjoint unions of complete graphs and is typically excluded from the definition; in either case the theorem statement assumes a connected $(k,a,b)$-SRG.) With both hypotheses verified, we conclude that $k$ is a simple eigenvalue of $A$, and the eigenspace $E_k = \mathbb{R} \mathbf{1}$. [/guided] [/step] [step:Show every eigenvector orthogonal to $\mathbf{1}$ satisfies $\lambda^2 + (b-a)\lambda + (b-k) = 0$] Since $A$ is real symmetric, eigenvectors for distinct eigenvalues are orthogonal. Let $\lambda \neq k$ be any other eigenvalue of $A$ with eigenvector $x \in \mathbb{R}^n \setminus \{0\}$. Then $x \perp \mathbf{1}$, so \begin{align*} Jx = \mathbf{1} \mathbf{1}^\top x = \mathbf{1} \cdot \langle \mathbf{1}, x \rangle = 0. \end{align*} Applying the matrix identity $(\star)$ to $x$, \begin{align*} A^2 x + (b-a) A x + (b-k) x = b J x = 0. \end{align*} Using $Ax = \lambda x$ and $A^2 x = \lambda^2 x$, \begin{align*} \big(\lambda^2 + (b-a) \lambda + (b-k)\big) x = 0. \end{align*} Since $x \neq 0$, we conclude \begin{align*} \lambda^2 + (b - a)\lambda + (b - k) = 0. \end{align*} Solving this quadratic by the standard formula gives the two roots \begin{align*} \lambda_\pm = \frac{(a - b) \pm \sqrt{(a - b)^2 + 4(k - b)}}{2}. \end{align*} Write $D := \sqrt{(a-b)^2 + 4(k-b)}$; note $(a-b)^2 + 4(k-b) \geq 0$ because $A$ is real symmetric and hence has real eigenvalues. [guided] The identity $(\star)$ holds as an equation of matrices in $\mathbb{R}^{n \times n}$. We now feed it an eigenvector to extract a scalar equation for $\lambda$. Which eigenvector? Any eigenvector $x$ for an eigenvalue $\lambda \neq k$. Why does this help? Because such an $x$ is orthogonal to $\mathbf{1}$, which kills the obstruction term $bJ$ on the right. Why is $x \perp \mathbf{1}$? The adjacency matrix $A$ is real symmetric (since $G$ is undirected), so [eigenvectors for distinct eigenvalues are orthogonal](/theorems/???). The eigenvector $\mathbf{1}$ belongs to eigenvalue $k$, and $x$ belongs to $\lambda \neq k$, so $\langle \mathbf{1}, x \rangle = 0$. Now compute $Jx$. The matrix $J = \mathbf{1} \mathbf{1}^\top$ is rank one, and $Jx = \mathbf{1}(\mathbf{1}^\top x) = \langle \mathbf{1}, x \rangle \mathbf{1} = 0$. Apply $(\star)$ to $x$: \begin{align*} A^2 x + (b-a) A x + (b-k) x = b J x = 0. \end{align*} Since $Ax = \lambda x$ and iterating $A^2 x = A(\lambda x) = \lambda^2 x$, \begin{align*} \lambda^2 x + (b-a) \lambda x + (b-k) x = 0. \end{align*} Factor $x$ (which is nonzero): \begin{align*} \lambda^2 + (b-a)\lambda + (b-k) = 0. \end{align*} Every eigenvalue of $A$ other than $k$ satisfies this single quadratic, so there are at most two such eigenvalues. Call them $\lambda_+, \lambda_-$; by the quadratic formula, \begin{align*} \lambda_\pm = \frac{-(b-a) \pm \sqrt{(b-a)^2 - 4(b-k)}}{2} = \frac{(a-b) \pm \sqrt{(a-b)^2 + 4(k-b)}}{2}. \end{align*} We note in passing that the discriminant $(a-b)^2 + 4(k-b)$ is non-negative: a real symmetric matrix has only real eigenvalues, so the quadratic must split over $\mathbb{R}$. We abbreviate $D := \sqrt{(a-b)^2 + 4(k-b)}$. [/guided] [/step] [step:Determine multiplicities $s, t$ from dimension and trace constraints] Let $s$ denote the multiplicity of $\lambda_+$ and $t$ the multiplicity of $\lambda_-$. Since $\mathbb{R}^n$ decomposes into eigenspaces (as $A$ is real symmetric) and the only eigenvalues are $k, \lambda_+, \lambda_-$ (with $k$ of multiplicity $1$), \begin{align*} s + t + 1 = n. \tag{dim} \end{align*} The trace of $A$ equals $\sum_{i=1}^n A_{ii} = 0$, since $G$ has no self-loops. On the other hand, the trace equals the sum of eigenvalues counted with algebraic multiplicity (which equals geometric multiplicity because $A$ is symmetric): \begin{align*} 0 = \operatorname{tr}(A) = k \cdot 1 + s \lambda_+ + t \lambda_-. \tag{tr} \end{align*} Solve the linear system $(\text{dim})$, $(\text{tr})$ for $s$ and $t$. From $(\text{dim})$, $t = n - 1 - s$. Substituting into $(\text{tr})$, \begin{align*} 0 = k + s \lambda_+ + (n - 1 - s)\lambda_- = k + (n-1)\lambda_- + s(\lambda_+ - \lambda_-). \end{align*} Using $\lambda_+ - \lambda_- = D$ and $\lambda_+ + \lambda_- = a - b$ (so $\lambda_- = \frac{(a-b) - D}{2}$), \begin{align*} s = -\frac{k + (n-1)\lambda_-}{D} = \frac{1}{2}\!\left((n-1) - \frac{(n-1)(b - a) - 2k}{D}\right). \end{align*} Wait — let us redo this algebra carefully. We have \begin{align*} s D &= -k - (n-1) \lambda_- = -k - (n-1) \cdot \frac{(a-b) - D}{2} \\ &= -k + \frac{(n-1)(b - a)}{2} + \frac{(n-1) D}{2}. \end{align*} Dividing by $D$, \begin{align*} s = \frac{1}{2}(n-1) + \frac{1}{2} \cdot \frac{(n-1)(b-a) - 2k}{D} = \frac{1}{2}\!\left((n-1) + \frac{(n-1)(b-a) - 2k}{D}\right). \end{align*} By symmetry (swapping $\lambda_+ \leftrightarrow \lambda_-$ swaps $s \leftrightarrow t$ and changes the sign of $D$), \begin{align*} t = \frac{1}{2}\!\left((n-1) - \frac{(n-1)(b-a) - 2k}{D}\right). \end{align*} [guided] We know the spectrum of $A$: it consists of $k$ with multiplicity $1$, $\lambda_+$ with some multiplicity $s$, and $\lambda_-$ with some multiplicity $t$. We now pin down $s$ and $t$ using two linear equations. **Equation 1 — dimension.** Since $A \in \mathbb{R}^{n \times n}$ is symmetric, it is diagonalisable by the [spectral theorem](/theorems/???), so the sum of dimensions of eigenspaces equals $n$. The only eigenvalues are $k, \lambda_+, \lambda_-$ (any other eigenvalue would have to satisfy the quadratic from the previous step, which has at most two roots). Thus \begin{align*} s + t + 1 = n. \end{align*} **Equation 2 — trace.** The diagonal entries $A_{ii}$ count the number of edges from $i$ to itself, which is $0$ because $G$ is a simple graph. So $\operatorname{tr}(A) = 0$. But the trace also equals the sum of eigenvalues with multiplicity (a consequence of the spectral theorem applied to the symmetric matrix $A$): \begin{align*} 0 = \operatorname{tr}(A) = 1 \cdot k + s \lambda_+ + t \lambda_-. \end{align*} **Solve the system.** Substitute $t = n - 1 - s$: \begin{align*} 0 = k + s \lambda_+ + (n-1-s)\lambda_- = k + (n-1)\lambda_- + s(\lambda_+ - \lambda_-). \end{align*} By Vieta's formulas applied to $\lambda^2 + (b-a)\lambda + (b-k) = 0$, the sum of the roots is $\lambda_+ + \lambda_- = -(b-a) = a - b$ and the difference is $\lambda_+ - \lambda_- = D$, so $\lambda_- = \frac{(a-b) - D}{2}$. Plugging in: \begin{align*} s D = -k - (n-1) \cdot \frac{(a-b) - D}{2} = -k + \frac{(n-1)(b-a)}{2} + \frac{(n-1) D}{2}. \end{align*} Divide by $D$ (which is nonzero unless the two eigenvalues coincide, a degenerate case): \begin{align*} s &= \frac{1}{2}(n-1) + \frac{(n-1)(b-a) - 2k}{2D} = \frac{1}{2}\!\left((n-1) + \frac{(n-1)(b-a) - 2k}{D}\right). \end{align*} The multiplicity $t$ follows by the dimension equation, or equivalently by swapping the sign of the square root (which swaps $\lambda_+$ and $\lambda_-$ and hence $s$ and $t$): \begin{align*} t = \frac{1}{2}\!\left((n-1) - \frac{(n-1)(b-a) - 2k}{D}\right). \end{align*} [/guided] [/step] [step:Conclude that $s$ and $t$ must be non-negative integers] Multiplicities of eigenvalues of a real symmetric matrix are non-negative integers. Therefore both \begin{align*} \frac{1}{2}\!\left((n-1) + \frac{(n-1)(b-a) - 2k}{\sqrt{(a-b)^2 + 4(k-b)}}\right), \qquad \frac{1}{2}\!\left((n-1) - \frac{(n-1)(b-a) - 2k}{\sqrt{(a-b)^2 + 4(k-b)}}\right) \end{align*} are non-negative integers, which is the stated integrality condition. (Noting that $b - a$ and $a - b$ differ only in sign, the sign convention inside the fraction matches the theorem statement.) This completes the proof. [/step]