Minimizing determinant(Ztranspose.A.Z) - MathOverflow

Minimizing determinant(Ztranspose.A.Z)

2011-03-07T00:09:07Z

Let $A$ be a fixed positive semi-definite symmetric $m\times m$ matrix, and let $p$ be a fixed positive integer. Let $Z$ vary over all $m\times p$ matrices with orthonormal columns, and denote the transpose of $Z$ by $Z^T$. How does one prove that the minimum of $\mbox{det}(Z^T.A.Z)$ is the product of the $p$ smallest eigenvalues of $A$?

I've seen this quoted in a few places, but the references cited have turned out to be either vacuous ("a little algebra shows") or encrusted with so much generality that I can't see through to the core of the proof. Does anyone have a good reference or a proof that is short enough to be given in this forum? Not surprisingly, I can prove it for $p=1$ and for $p=m$.

And is there an analogous result when "minimum" is replaced by "maximum"?

Does anyone know to whom these results are due? They are probably pretty ancient.

Answer by David Bar Moshe for Minimizing determinant(Ztranspose.A.Z)

2011-03-07T14:03:42Z

The following method reduces the problem to the known case $p=1$.

Notice that $P_Z \equiv ZZ^t$ is an orthogonal projector of rank $p$, thus:

$\det(Z^t A Z) = \det( I_p + Z^t(A-I_m)Z) = \det( I_m + ZZ^t(A-I_m)ZZ^t) = \det( I_m + P_Z(A-I_m)P_Z)$

Where, $I_p$, $I_m$ are the $p$ and $m$ dimensional unit matrices. The second equality is due to the fact that the matrices $Z^t(A-I_m)Z$, $ZZ^t(A-I_m)ZZ^t$ have the same secular coefficients, by cyclic permutations and the identity $Z^tZ = I_p$.

Denote by $\rho(A)$ the completely antisymmetric $p$-tensor product representation of $A$:

$\rho(A) \circ v_1 \wedge . . . \wedge v_p = Av_1 \wedge . . . \wedge A v_p$

We have:

$\det( I_m + P_Z(A-I_m)P_Z) = \mbox{tr} (\rho(P_Z) \rho(A))$

(Both sides are equal, because they are just the determinant of the restriction of A to the range of $P_Z$.

Now,$\rho(P_Z)$ is a one dimensional projector over the $p$-wedge product of the range of $P_Z$, and the eigenvalues of $\rho(A)$ are just all possible products of $p$ distinct eigenvalues. By the known rank one solution, the absolute minimum is the minimal eigenvalue of $\rho(A)$ which is the product of the $p$ smallest eigenvalues of $A$.

Answer by Sergei Ivanov for Minimizing determinant(Ztranspose.A.Z)

2011-03-07T14:54:12Z

A stronger fact holds: If $\lambda_1\le\lambda_2\le\dots\le\lambda_m$ are the eigenvalues of $A$, and $\mu_1\le\mu_2\le\dots\le\mu_p$ are eigenvalues of $Z^TAZ$, then $\mu_k\ge\lambda_k$ for all $k=1,\dots,p$. Update: This fact is well-known as Cauchy interlacing theorem.

Proof. Let $Q$ be the quadratic form on $\mathbb R^m$ defined by $A$ (that is, $Q(x)=x^TAx$ for all $x\in\mathbb R^m$), $L:\mathbb R^p\to\mathbb R^m$ the (isometric) linear map defined by $Z$. Then $Z^TAZ$ is the matrix of the quadratic form $Q'$ on $\mathbb R^p$ given by $Q'(x)=Q(L(x))$. I suggest you think of $Q'$ as the restriction of $Q$ to the subspace $L(\mathbb R^p)$ of $\mathbb R^m$.

Suppose that $\mu_k<\lambda_k$ for some $k$. Let $V$ be the $k$-dimensional subspace of $\mathbb R^p$ spanned by the first $k$ eigenvectors of $Q'$. Then $Q'(x)\le \mu_k |x|^2$ for all $x\in V$. Let $W$ be the $(m-k+1)$-dimensional subspace of $\mathbb R^m$ spanned by the eigenvectors corresponding to $\lambda_k,\lambda_{k+1},\dots,\lambda_m$. Then $Q(x)\ge\lambda_k|x|^2$ for all $x\in W$. The subspaces $W$ and $L(V)$ have nonzero intersection since the sum of their dimensions is greater than $m$. Hence there exists a nonzro vector $x\in V$ such that $L(x)\in W$. For this vector, we have $Q'(x)\le \mu_k |x|^2 <\lambda_k|x|^2$ but $Q'(x)=Q(L(x))\ge \lambda_k|L(x)|^2=\lambda_k|x|^2$, a contradiction. Q.E.D.

Similarly (inverting all inequalities in the argument) one sees that the $k$-th largest eigenvalue of $Q'$ is no greater than the $k$-th largest eigenvalue of $Q$, answering your second question.