# Minimizing determinant(Ztranspose.A.Z)

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.

• Does using Lagrange multipliers and looking for the critical points not work? – Deane Yang Mar 7 '11 at 0:29
• Also, doesn't it suffice to prove this when $A$ is diagonal? – Deane Yang Mar 7 '11 at 3:42

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.

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