Construct a diagonal-1 gram matrix with given eigenvalues

Question

I got a question concerning positive semidefinite matrices. Given a positive semidefinite matrix $M\in \mathbb{R}^{n\times n}$, we know that its trace $\text{tr}(M)$ equals to the sum of its eigenvalues. Now I have a gram matrix $M\in \mathbb{R}^{n\times n}$ with $1$ as its diagonal elements. Then $$ \text{tr}(M) = \lambda_1 + \cdots +\lambda_n = n. $$ Here $\lambda_1\ge\cdots\ge\lambda_n$ are eigenvalues of $M$. We consider the converse of the problem: given $\mu_1\ge\cdots\ge\mu_n$, with $\sum_{i=1}^n \mu_i = n$, can we construct a diagonal-1 gram matrix with $\mu_1\ge\cdots\ge\mu_n$ as its eigenvalues?

My Trials:

1. For $n=2$ this is true, since the matrix \begin{pmatrix} 1 & a \\ a & 1 \end{pmatrix} has eigenvalues $1+a$ and $1-a$, for $a\in[-1,1]$. This might be useful for induction.

2. The diagonal-1 gram matrices form a convex, compact space(denoted by $T$). The mapping $\mathcal{A}:T\to U=\{\vec{\mu}\in\mathbb{R}^n:\sum_{i=1}^n\mu_i=n,~\mu_1\ge\cdots\ge\mu_n\ge0\}$, that sends $M$ to it ordered eigenvalues, is continuous. This shows that at least the $i$-th eigenvalue of $M$ can range from $1$ to $n$ for $i=1$, and $0$ to $n/i$ for $i\ge 1$ by intermediate value theorem . But seems hard for generalization. How to prove $\mathcal{A}$ is surjective?

3. An important characterization of eigenvalues is the Courant-Fisher theorem. I considered this but didn't get further inspiration.

4. $M = \Gamma'\Gamma$, where $\Gamma=[\gamma_1,\cdots,\gamma_n]$. Since the diagonal entries of $M$ are all one, $\|\gamma_i\|=1$. If we consider the quadratic form $\beta'M\beta$ with $\|\beta\|=1$, the resulting surface is an ellipsoid whose semi-axes are determined by the eigenvalues of $M$. This inspires me that there is a geometric correspondence between an arbitrary group of unit bases \in $\mathbb{R}^n$ and ellipsoids whose semis-axes satisfies the condition $\sum_{i=1}^n(1/a_i^2)=n$. So I guess this conclusion is very likely to be correct. Could anyone offer a rigorous proof? Thanks!

Answer 1

This can be proved to be correct via Schur-Horn's Theorem!! The majorization trick is so amazing. See the classic, Matrix Analysis!

Answer 2

I think your point 2 can be turned into a proof.

Here is an sketch Let $T_n$ be the set of all Gram matrices with diagonal $1$. Since a gram matrix, is given by $[\langle v_i, v_j \rangle]_{i,j}$ for some set of vectors $v_j$ and we are assuming that $\| v_j \| = 1$, every gram matrix in $T$ is the image of $n$-points in the sphere $S^{n - 1}$. But, two sets of points $v_j$ and $w_j$ give the same gram matrix iff there is a transformation $S \in O(n)$ such that $w_j = S(v_j)$. Therefore we can identify the set of gram matrices $T_n$ with $$ \underbrace{S^{n-1} \times S^{n-1} \times ... S^{n-1}} _{n \mbox{ times}} \, / O(n) \to T_n. $$ That quotient is an space with an interior, the image under the quotient of the points in the sphere without geodesic co-linearities (you can think of this as the analogue in sphere geometry of being linearly independent). The codimension $1$ "faces" would be the point configurations in which all points lay in a geodesic submanifold of $S^{n-1}$ of codimension $1$, the same can be done for other codimensions. This will give you a $CW$-complex structure over the closure of the natural cross-section of the quotient. Now, if you want to apply the "intermediate value theorem" you need to see that the map $A: T \to U$ sends $\partial T$ surjectively on $\partial U$. If two sets have the same dimension and a continuous map is surjective in the boundary, then it is surjective. Now, you can apply induction from your point $1$, since the points in the boundary live in a product of spheres of dimension $n - 1$, the map $A{|}_{\partial T_n}$ can be identified with the map $A: T_{n-1} \to U_n$ (modulo renormalizing the simplex, so that the trace is $1$ and not $n$.