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?)

  • 4
    $\begingroup$ 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?). $\endgroup$
    – Samuele
    May 18, 2021 at 5:51
  • 1
    $\begingroup$ 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. $\endgroup$ May 18, 2021 at 8:43
  • 1
    $\begingroup$ Sorry, the constant term is $-4e_1^2 e_4$. $\endgroup$ May 18, 2021 at 8:50
  • 1
    $\begingroup$ 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. $\endgroup$ May 18, 2021 at 9:29
  • 1
    $\begingroup$ arxiv.org/pdf/1003.0475.pdf $\endgroup$ May 18, 2021 at 14:29

4 Answers 4


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<j\leq n} (\lambda_i-\lambda_j)^2,$$ 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).

  • 2
    $\begingroup$ 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. $\endgroup$ May 19, 2021 at 1:28
  • $\begingroup$ I've added an explicit solution as an answer below. $\endgroup$ May 20, 2021 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.


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.

  • 3
    $\begingroup$ 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? $\endgroup$
    – user178596
    May 18, 2021 at 13:24
  • $\begingroup$ @LucelliaKassel Yes, I got mixed up between the two matrices. $\endgroup$
    – Random
    May 19, 2021 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.