Prove that the Eigenvalues of this Matrix are in [0,1 ]

Question

Let $E,F \subset \mathbb{R^n}$

Note that $< . >$ defines the Inner product on $\mathbb{R^n}$

Let $(e_1,....,e_k)$ and $(f_1,.....f_l$) be Orthonormal bases of E and F respectively.

Consider the Matrix $A=(<e_i,f_j>)$ of size $k*l$

Let $\lambda_i$ be an Eigenvalue of $A^T A$

Prove that $\lambda_i \in [0, 1] \; \; \forall i$ and that they do not depend on the choice of bases of $E$ and $F$

I tryed experimenting on a small dimension matrix but I'm not able to figure it out. Thoughts?

Answer 1

If $V$ is any inner product space and $W$ is a subspace, then there is a natural orthogonal projection map $P_W:V \to W$. These projections have several important properties. Among these we can show that $P_W$ has operator norm equal to $1$ and is positive-semidefinite. (http://en.wikipedia.org/wiki/Hilbert_space#Orthogonal_complements_and_projections)

We will consider the maps $P_E: \mathbb{R}^n \to E$ and $P_F: \mathbb{R}^n \to F$, and in particular we will consider the restrictions of these maps to appropriate subspaces.

Specifically, notice that $A^t$ is the matrix for $P_F|_E:E \to F$ with respect to the bases $(e_1,\dots,e_k)$ and $(f_1,\dots,f_l)$. Also notice that $A$ is the matrix for $P_E|_F:F \to E$ with respect to the bases $(f_1,\dots,f_l)$ and $(e_1,\dots,e_k)$. This can be easily computed using the definition of the matrix for a linear map and the properties of these projections.

It follows that $A^tA$ is the matrix for the map $P=P_F \circ P_E: F \to F$ with respect to the basis $(f_1, \dots, f_l)$. Since $P_E$ and $P_F$ have operator norm equal to $1$, it follows that $P$ has operator norm less than or equal to 1. Thus, all eigenvalues have absolute value less than or equal to $1$. But $P$ is also a positive semidefinite operator on $F$ (because for any $v \in F$, we have that $\langle Pv,v \rangle = \langle P_Ev, P_Fv \rangle = \langle P_Ev, v \rangle = ||P_Ev||^2\geq 0$), and thus the eigenvalues of $P$ must be non-negative. Then it immediately follows that the eigenvalues of $P$ (and thus $A^tA$) must be in $[0,1]$.

These eigenvalues only depend on the maps $P_E$ and $P_F$. In other words these eigenvalues only depend on the subspaces $E$ and $F$, and not the choices of bases. Also notice that this could have been done in any inner product space. Nothing special about $\mathbb{R}^n$ or the dot product.

Answer 2

Write $M_{E}$ as the matrix with the columns $e_j$ and $M_{F}$ as the matrix with the columns $f_j$, then notice that $A = M_E^T M_F$. Notice we are searching for $\left\|A \right\| = \sqrt{\lambda_{max}(A^TA)}$ and trying to show that it is less than $1$. Now $\left\|A\right\| \leq \left\|M_E \right\| \left\|M_F\right\|$ and since $M^T_E M_E = I_k$, $M^T_F M_F = I_l$ we have $\left\|M_E \right\| = 1 , \left\|M_F \right\| = 1$ and finally yield $\left\|A\right\| \leq 1 $.