# How to show a $3\times3$ matrix has three distinct eigenvalues?

Here is a question I heared from others:

Given four distinct positive real numbers $$a_1,a_2,a_3,a_4$$ and set $$a:=\sqrt{\sum_{1\leq i\leq 4}a_i^2}$$ $$A=(x_{i,j})_{1\leq i\leq3,1\leq j\leq4}$$ is a $$3\times4$$-matrix specified by $$x_{i,j}=a_i\delta_{i,j}+a_j\delta_{4,j}-\frac{1}{a^2}(a_i^2+a_4^2)a_j$$ where $$\delta_{i,j}$$ is the Kronecker symbol or visually $$A=\begin{pmatrix}a_1 &0&0&a_4\\ 0&a_2&0&a_4\\0&0&a_3&a_4\end{pmatrix}-\frac{1}{a^2} \begin{pmatrix} a_1(a_1^2+a_4^2) & a_2(a_1^2+a_4^2) & a_3(a_1^2+a_4^2) & a_4(a_1^2+a_4^2)\\ a_1(a_2^2+a_4^2) & a_2(a_2^2+a_4^2) & a_3(a_2^2+a_4^2) & a_4(a_2^2+a_4^2)\\ a_1(a_3^2+a_4^2) & a_2(a_3^2+a_4^2) & a_3(a_3^2+a_4^2) & a_4(a_3^2+a_4^2)\\ \end{pmatrix}$$

The question is to show that the $$3\times3$$-matrix $$B=AA^T$$ admits three distinct eigenvalues.($$A^T$$ is the transpose of $$A$$)

What I am curious about is how many methods can be utilized to show a matrix has different eigenvalues?

As for this question my idea is to calculate the characteristic polynomial $$f$$ of $$B$$ along with $$f'$$ which is a quadratic polynomial via Sagemath and show that neither of roots of $$f'$$ belongs to $$f$$. Or equivalently to calculate the resultant $$R(f,f')$$ of $$f$$ and $$f'$$ and show that $$R(f,f')$$ doesn't vanish for any distinct positive $$a_i$$'s.

But the difficulties are both ways involve hideous calculation which I don't think I can write down by hand. So I'm wondering if there is a tricky way to get to that point? (e.g. an algebraic-geometry method?)

• Well, the matrix is not as terrible as it looks: $A=A_1-\frac{1}{\lambda}ba^t$ with $A_1$ a $3\times 4$ matrix, $b\in\mathbb R^3$, $a\in\mathbb R^4$ and $\lambda=\|a\|^2$. Moreover, $A_1a=b$, so $AA^t=A_1A_1^t - \frac{1}{\lambda}bb^t$. And finally $$A_1A_1^t=\begin{pmatrix}a_1^2+a_4^2&a_4^2&a_4^2\\a_4^2&a_2^2+a_4^2&a_4^2\\a_4^2&a_4^2&a_3^2+a_4^2\end{pmatrix}$$ ... so maybe the computation is not that terrible (perhaps, with Gershgorin circle theorem?). May 18 at 5:51
• Let $e_j$ be the $j$-th elementary symmetric function of $a_1^2,a_2^2,a_3^2,a_4^2$. Then the characteristic polynomial of $a^2 AA^T$ is $x^3 - 2e_2 x^2 + 3 e_1e_3x - 4e_1^2e^4$. Not sure what to do next. May 18 at 8:43
• Sorry, the constant term is $-4e_1^2 e_4$. May 18 at 8:50
• In terms of the symmetric functions, the resultant is $$108 e_1^3e_3^3 - 36 e_1^2e_2^2e_3^2 - 432e_1e_2^3e_3e_4 + 128e_2^5e_4 + 432e_2^4e_4^2.$$ I'll try some other bases. May 18 at 9:29
• arxiv.org/pdf/1003.0475.pdf May 18 at 14:29

To answer on methods applicable here (and elaborate on comments I made). The most promising is to use a surprisingly little-known theorem that says that the discriminant $$D$$ of a symmetric $$n\times n$$ matrix $$A=(a_{ij})$$ with eigenvalues $$\lambda_1,\dots,\lambda_n$$, i.e. $$D_A=\prod_{1\leq i is a sum of squares in the ring $$\mathbb{R}[a_{11},a_{12},\dots,a_{nn}]$$ (notice that $$D_A$$ is nonnegative, as all $$\lambda_k$$ are real). This has been proved independently by a number of authors, e.g. in a paper by P.Lax.

An explicit formula for such an expression for $$n=3$$ may be found in Sect. 4 of B.Parlett's paper.

This is a rather surprising result for everyone familiar with the fact that most nonnegative multivariate polynomials are not sums of squares (this topic has history going back to a famous paper by Hilbert from 1888).

• I've computed an actual representation of the discriminant as the sum of squares, and verified that setting them all to zeros implies that equality of some pair of $a_i$. So, the problem is settled. May 19 at 1:28
• I've added an explicit solution as an answer below. May 20 at 3:11

Here is an explicit solution found computationally (and then beautified) using the approach referenced by Dima.

Let $$f(x,y,z,t) := (x-y) (z-t) (xy(z+t) - (x+y)zt),$$ $$g(x,y,z,t) := (x-y) (z-t) (xy(z-t) + (x-y)zt).$$ Then the discriminant in question equals $$2a^{-8}(7s_1 + s_2),$$ where $$s_1:= f(a_1^2,a_2^2,a_3^2,a_4^2)^2 + f(a_1^2,a_3^2,a_2^2,a_4^2)^2 + f(a_2^2,a_3^2,a_1^2,a_4^2)^2$$ and $$s_2:= g(a_1^2,a_2^2,a_3^2,a_4^2)^2 + g(a_1^2,a_3^2,a_2^2,a_4^2)^2 + g(a_2^2,a_3^2,a_1^2,a_4^2)^2 + g(a_3^2,a_2^2,a_1^2,a_4^2)^2 + g(a_1^2,a_1^2,a_3^2,a_4^2)^2 + g(a_3^2,a_1^2,a_2^2,a_4^2)^2.$$ (Btw, it can be verified that both $$s_1$$ and $$s_2$$ represent symmetric polynomials in $$a_1^2,a_2^2,a_3^2,a_4^2$$.)

Now, we see that the discriminant as the sum of squares can be zero only when all these squares are zero. Since $$a_i$$ are pairwise distinct, we can cancel the first two (linear) factors in $$f,g$$ and focus on third factors being zero. However, in the ideal generated by these factors, there is a polynomial (I checked the first one in the Grobner basis) that is nonzero for distinct nonzero $$a_i$$, meaning that all squares cannot be zero at the same time.

So, the discriminant is strictly positive.

PS. In fact, $$s_2$$ alone cannot be zero for pairwise distinct $$a_i$$.

EDIT: I got mixed up, but I wrote some partial progress using an idea of @Geoff Robinson in a deleted answer (if I have time I will try to finish this). I keep the old "solution" because it is perhaps interesting in itself.

FAKE SOLUTION: As @Samuele has commented we need to show that the matrix $$\begin{pmatrix} a_{1}^2 + a_{4}^2 && a_{4}^2 && a_{4}^2 \\ a_{4}^2 && a_{2}^2 + a_{4}^2 && a_{4}^2 \\ a_{4}^2 && a_{4}^2 && a_{3}^2 + a_{4}^2 \end{pmatrix}$$ has distinct eigenvalues. Scaling the matrix by $$a_{4}^2$$ we can assume that $$a_{4} = 1$$. Now, substituting $$b_i = a_{i}^2 + 1, i = 1, 2, 3$$ and subtracting the identity matrix we need to show that $$\begin{pmatrix} b_1 && 1 && 1 \\ 1 && b_2 && 1 \\ 1 && 1 && b_3 \end{pmatrix}$$ has distinct eigenvalues for all distinct real numbers $$b_1, b_2, b_3$$. The characteristic polynomial is $$(x + b_1)(x + b_2)(x + b_3) - (x + b_1) - (x + b_2) - (x + b_3) + 2$$ Notice that by translating the $$b_i$$ by a constant we can assume without loss of generality that 0 is an eigenvalue, that is $$b_1 b_2 b_3 - b_1 - b_2 - b_3 + 2 = 0$$ This means that the characteristic polynomial is $$x \left( x^2 + (b_1 + b_2 + b_3) x + (b_1 b_2 + b_1 b_3 + b_2 b_3 - 3) \right)$$ If 0 is a root of the quadratic factor, then $$b_1 b_2 + b_1 b_3 + b_2 b_3 - 3 = 0$$. Therefore, we have $$(x + b_1)(x + b_2)(x + b_3) = x^3 + (b_1 + b_2 + b_3) x^2 + 3 x + (b_1 + b_2 + b_3 - 2)$$ However, the discriminant of this polynomial is a polynomial of degree 4 in $$b_1 + b_2 + b_3$$, which Wolfram Alpha says is always non-positive, and therefore the polynomial never has 3 distinct real roots which is a contradiction.

(Explicitly, substituting $$e_1 = b_1 + b_2 + b_3$$ the polynomial is $$- 4 (e_1 - 3)^2 \left( (e_1 + 2)^2 + 2 \right)$$, and we see that equality happens exactly when $$b_1 = b_2 = b_3 = 1$$).

Now, it is sufficient to show that the quadratic $$x^2 + (b_1 + b_2 + b_3) x + (b_1 b_2 + b_1 b_3 + b_2 b_3 - 2)$$ has distinct roots. If this is not the case, looking at the discriminant we get $$(b_1 + b_2 + b_3)^2 = 4 \left( b_1 b_2 + b_1 b_3 + b_2 b_3 \right) - 12$$ And now we have $$(x + b_1) (x + b_2) (x + b_3) = x^3 + (b_1 + b_2 + b_3) x^2 + \left( \frac{(b_1 + b_2 + b_3)^2 + 12}{4} \right) x + (b_1 + b_2 + b_3 - 2) = 0$$ Substituting $$u = b_1 + b_2 + b_3$$, the discriminant is $$- \frac{1}{4} (u + 6)^2 ((u - 4)^2 + 8)$$ which is non-positive, and therefore the polynomial never has 3 distinct real roots.

PARTIAL PROGRESS:

After our normalization of $$a_4 = 1$$ and substituting $$b_i = a_{i}^2 + 1$$ our matrix is $$A A^t = \begin{pmatrix} b_1 && 1 && 1 \\ 1 && b_2 && 1 \\ 1 && 1 && b_3 \end{pmatrix} - \frac{1}{\lambda} b b^t$$ where $$b = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix}$$ Suppose by contradiction that $$A A^t$$ did not have distinct eigenvalues. Then there would be an eigenvalue $$\mu$$ whose eigenspace would be 2-dimensional. Notice that $$b b^t$$ is a matrix of rank 1, and therefore its kernel is 2-dimensional. This means that there is an vector $$u = \begin{pmatrix} u_1 \\ u_2 \\ u_3 \end{pmatrix}$$ in the intersection of the $$\mu$$ eigenspace of $$A A^t$$ and the kernel of $$b b^t$$, which means that $$b_1 u_1 + b_2 u_2 + b_3 u_3 = 0$$ $$b_1 u_1 + u_2 + u_3 = \mu u_1$$ $$u_1 + b_2 u_2 + u_3 = \mu u_2$$ $$u_1 + u_2 + b_3 u_3 = \mu u_3$$ Adding the last three equations and subtracting the first we get that $$2 (u_1 + u_2 + u_3) = \mu (u_1 + u_2 + u_3)$$ and therefore either $$\mu = 2$$ or $$u_1 + u_2 + u_3 = 0$$.

$$\textbf{Case i}$$: $$u_1 + u_2 + u_3 = 0$$ In this case we get that $$(b_i - 1) u_i = \mu u_i$$ for $$i = 1, 2, 3$$, and so for each $$i$$ either $$u_i = 0$$ or $$b_i - 1 = \mu$$. However, as the $$b_i$$ are distinct we must have that for at least 2 $$i$$'s $$u_i = 0$$. But since the sum of the $$u_i$$ are 0 we must have that all of the $$u_i$$'s are zero, which is a contradiction.

$$\textbf{Case ii}$$: $$\mu = 2$$ Let the eigenvalues of $$A A^t$$ be $$2, 2, \eta$$ for some $$\eta \in \mathbb{R}$$. We can compute the trace and the determinant of $$\begin{pmatrix} b_1 && 1 && 1 \\ 1 && b_2 && 1 \\ 1 && 1 && b_3 \end{pmatrix} - \frac{1}{\lambda} b b^t$$ relatively easy using the linearity of trace and the matrix determinant lemma. This gives us two identities on $$\eta$$, which should be enough to finish.

• In Samuele's comment, $A_1A_1^t$ is just a part of $AA^t$. So I'm wondering how to utilize the fact of $A_1A_1^t$ as shown by you to deduce $AA^t$ has different eigenvalues?
– user178596
May 18 at 13:24
• @LucelliaKassel Yes, I got mixed up between the two matrices. May 19 at 0:42

This question is from this year's Alibaba mathematics competition (qualifying round, which is finished 2 days ago), and here's my solution that could be wrong (I also participated in the competition and this is the solution I submitted). I tried to solve the problem geometrically to avoid tons of computations.

First, we can deal with $$A^{T}A$$ instead of $$AA^{T}$$ since the first matrix's eigenvalues is same as the second eigenvalue's matrix with zero (consider SVD of $$A$$). The key point is that $$A$$ can be written as $$A = BP$$ where $$B = \begin{pmatrix} a_1 & 0 & 0 & a_4 \\ 0 & a_2 & 0 & a_4 \\ 0 & 0 & a_3 & a_4 \end{pmatrix}$$ and $$P = I_3 - \mathbf{v}\mathbf{v}^{T}, \mathbf{v} = \frac{1}{a}(a_1, a_2, a_3, a_4)^{T}.$$ Especially, the matrix $$P$$ is an orthogonal projection matrix that project a vector in $$\mathbb{R}^{4}$$ to the subspace of vectors that are perpendicular to $$\mathbf{v}$$. It satisfies $$P^{T} = P^{2} = P$$.

To show that the eigenvalues are distinct, we will show that each eigenspace (for nonzero eigenvalues) has dimension 1. In other words, for a given eigenvalue, there exists a unique eigenvector (up to constant factor) corresponding to the eigenvalue.

First, the above $$\mathbf{v}$$ is an eigenvector of $$A^{T}A$$ correspond to the eigenvalue 0 since $$A\mathbf{v} = BP\mathbf{v} = \mathbf{0}$$. Since the eigenvectors are orthogonal to each other, the other three eigenvectors are in the image of $$P$$ (the hyperplane perpendicular to $$\mathbf{v}$$). If we fix an (nonzero) eigenvalue $$\lambda$$ and a corresponding eigenvector $$\mathbf{w}$$, we have $$P\mathbf{w} = \mathbf{w}$$ and so $$A^{T}A\mathbf{w} = PB^{T}BP\mathbf{w} = PB^{T}B\mathbf{w} = \lambda \mathbf{w}.$$ From this, the vector $$B^{T}B\mathbf{w}$$ should be written as $$B^{T}B\mathbf{w} = \lambda \mathbf{w} + \beta \mathbf{v}$$ for some $$\beta$$. If we set $$\mathbf{w} = (x_1, x_2, x_3, x_4)^{T}$$, then expanding the above equation gives $$\begin{pmatrix}a_1^2 & 0 & 0 & a_{1}a_{4} \\ 0 & a_{2}^{2} & 0 & a_{2}a_{4} \\ 0 & 0& a_{3}^{2} & a_{3}a_{4} \\ a_{1}a_{4} & a_{2}a_{4} & a_{3}a_{4} & 3a_{4}^{2} \end{pmatrix}\mathbf{w} = \begin{pmatrix} a_{1}^{2}x_{1} + a_{1}a_{4}x_{4} \\ a_{2}^{2}x_{2} + a_{2}a_{4}x_{4} \\ a_{3}^{2}x_{3} + a_{3}a_{4}x_{4} \\ a_{4}(a_{1}x_{1} + a_{2}x_{2} + a_{3}x_{3} + 3a_{4}x_{4})\end{pmatrix} = \begin{pmatrix} a_{1}^{2}x_{1} + a_{1}a_{4}x_{4} \\ a_{2}^{2}x_{2} + a_{2}a_{4}x_{4} \\ a_{3}^{2}x_{3} + a_{3}a_{4}x_{4} \\ 2a_{4}^{2}x_{4}\end{pmatrix} = \begin{pmatrix} \lambda x_1 + \beta' a_1 \\ \lambda x_2 + \beta' a_2 \\ \lambda x_3 + \beta' a_3 \\ \lambda x_4 + \beta' a_4\end{pmatrix}, \quad \beta' = \frac{\beta}{a}$$ Here we used $$\langle \mathbf{v}, \mathbf{w} \rangle = a_{1}x_{1} + \cdots + a_{4}x_{4} = 0$$ for the second equality. From this, we can show that $$x_{4}$$ should be nonzero (here's the point that distinctiveness of $$a_i$$'s are used), so we can assume that $$x_4 = 1$$ and the other components $$x_1, x_2, x_3$$ are uniquely determined. This proves our claim that each eigenspace has dimension 1, i.e. the eigenvalues are distinct.