7
$\begingroup$

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

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

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

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

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • 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 at 13:24
  • $\begingroup$ @LucelliaKassel Yes, I got mixed up between the two matrices. $\endgroup$
    – Random
    May 19 at 0:42
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy