Tackling an eigenvalue inequality
The International Mathematics Competition for University Students (IMC) is an annual competition generally hosted in Bulgaria. The paper consists of 10 problems, split between two sessions. This year, problem 8 was an inequality involving the eigenvalues of a real symmetric matrix. The statement reads as follows:
Problem 8. Let $n \geq 5$, and suppose that $A=\left(a_{i j}\right)$ is a real symmetric $n \times n$ matrix such that
\[a_{i i}=0 \quad \text { and } \quad a_{i j} \in\{-1,1\} \text { for } i \neq j .\]Assume that the scalar products of any two distinct rows of $A$ have the same value. Let $\lambda_1, \ldots, \lambda_n$ be the eigenvalues of $A$. Prove that
\[\sum_{i=1}^n\left|\lambda_i\right| \geq 2 n-2\]and determine all matrices for which equality holds.
At first glance, the problem looked quite approachable, especially for me, who needs to brush up on linear algebra. Here’s my thought process.
Solution. Well, the diagonal entries are nil, which means that the trace of $A$ is zero. At least we know that the sum of the eigenvalues is zero. The condition on the scalar product of any two distinct rows did not appear immediately clear to me, until I realized that it implies that:
\[A'A = \begin{bmatrix} n-1 & k & \cdots & k \\ k & n-1 & \cdots & k \\ \vdots & \vdots & \ddots & \vdots \\ k & k & \cdots & n-1 \end{bmatrix}\]where $k$ is the common value of the scalar products of any two distinct rows of $A$. Note that the diagonal elements are equal to $n-1$ since $a_{ii}=0$ and $a_{ij}^2=1$ for $i\neq j$. Also, it has to be the case that $k\leq n-2$, since different rows have exactly one zero element in different positions. The matrix $A’A$ looks nice, so I guessed that there should be an explicit formula for its determinant and we could infer its eigenvalues, which end up being the squares of the eigenvalues of $A$! This is the core of the steps below.
Claim 1. The eigenvalues of $A’A$ are $(n-1)(k+1)$ with multiplicity 1 and $n-k-1$ with multiplicity $n-1$.
Proof. A sort of brute force to verify this is to find the characteristic polynomial inductively. Let us simplify the problem a bit. Consider the matrix:
\[B_{m \times m}= \begin{bmatrix} a & 1 & \cdots & 1 \\ 1 & a & \cdots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & a \end{bmatrix}\]and we prove by induction on $m$ that $\det B = (a-1)^{m-1}(a+m-1)$. The base cases follow straightforwardly when we set $m=2$ and $m=3$. As inductive hypothesis, assume the expression above is true and we prove it also holds for $m+1$. This is not hard, as we can use the Laplace expansion on the first row of $B$:
\[|B|= a(a-1)^{m-1}(a+m-1) + \sum_{i=2}^{m+1}C_{1i}\]where $C_{1i}$ is the cofactor of the $i$-th element on the first row of $B$. However, we realize that all these cofactors are equal to $-(a-1)^{m-1}$ because the submatrices they are determinants of are row permutations of each other. As a result:
\[\begin{align*} |B| &= a(a-1)^{m-1}(a+m-1) - m (a-1)^{m-1}\\ &= (a-1)^{m-1}(a(a+m-1)-m)\\ &= (a-1)^{m-1}(a+m)(a-1)\\ &= (a-1)^{m}(a+m) \end{align*}\]as desired. Now, we can use this result to find the eigenvalues of $A’A$. Setting $a=\frac{n-1}{k}$ and $m=n$, we get after rescaling accordingly:
\[\det{(A'A-\lambda I_n)} = (-1)^n(\lambda - (n-1)(k+1))(\lambda - (n-k-1))^{n-1}\]which implies the required assertion. $\square$
The above proof is correct and all, but it is not the most elegant one, if you ask me. A cleaner one can be found if we note that $A’A$ can be expressed as \(A'A=(n-k-1)I_{n} + k J_{n}\) where $J_n$ is the all-ones matrix. The eigenvalues of $kJ_n$ are $0$ with multiplicity $n-1$ and $kn$ with multiplicity 1. Shifting these values by $n-k-1$ gives us the eigenvalues of $A’A$, as required. Short and beautiful, isn’t it?
Anyway, the problem reduces to proving the inequality for the eigenvalues, which we now know. Using our Claim 1, we learn that
\[\begin{align*} \sum_{i=1}^n|\lambda_i| &= \sqrt{(n-1)(k+1)} + (n-1)\sqrt{n-k-1} \\ &\geq 2 \sqrt{(n-1)^{3/2}\left[(n-k-1)(k+1)\right]^{1/2}} \\ &\geq 2(n-1) \end{align*}\]where the inequality in the second row follows from the celebrated AM-GM inequality, and the third line comes from the fact that for $0 \leq k \leq n-2$, we have $(n-k-1)(k+1) \geq n-1$. (Note that since $A’A$ is positive semi-definite, its eigenvalues are non-negative, so $k \geq -1$. In the edge case where $k=-1$, the sum of absolute eigenvalues is $(n-1)\sqrt{n}$, which is strictly greater than $2(n-1)$ for $n \geq 5$). We are so done!
Not so fast, my friend! We need to find all the matrices for which the equality holds. The AM-GM inequality gives an equality if and only if both terms are equal, that is, $\sqrt{(n-1)(k+1)} = (n-1)\sqrt{n-k-1}$. Squaring both sides and dividing by $n-1$ (since $n \geq 5$) yields $k+1 = (n-1)(n-k-1)$, which simplifies to $n(n-k-2) = 0$. This implies equality holds exactly when $k=n-2$.
What does a matrix with $k=n-2$ look like? The scalar product of any two distinct rows $i$ and $j$ is the sum of $n-2$ terms of the form $a_{im}a_{jm}$ (since $a_{ii}=a_{jj}=0$). Because $a_{ij} \in {-1, 1}$, the only way this sum can reach $n-2$ is if $a_{im}a_{jm} = 1$ for all $m \neq i,j$, meaning $a_{im} = a_{jm}$. Using the symmetry of $A$, this forces all off-diagonal entries of $A$ to be identical. Hence, the only matrices for which equality holds are $A = J_n - I_n$ and $A = -(J_n - I_n)$. $\square$
Interested in more problems? You can find the full paper for IMC 2026 and other years here.