Minimizing determinant(Ztranspose.A.Z) - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T18:55:08Z http://mathoverflow.net/feeds/question/57619 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57619/minimizing-determinantztranspose-a-z Minimizing determinant(Ztranspose.A.Z) David Epstein 2011-03-07T00:09:07Z 2011-03-07T15:36:00Z <p>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$?</p> <p>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 <em>good</em> 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$.</p> <p>And is there an analogous result when "minimum" is replaced by "maximum"?</p> <p>Does anyone know to whom these results are due? They are probably pretty ancient.</p> http://mathoverflow.net/questions/57619/minimizing-determinantztranspose-a-z/57668#57668 Answer by David Bar Moshe for Minimizing determinant(Ztranspose.A.Z) David Bar Moshe 2011-03-07T14:03:42Z 2011-03-07T14:18:45Z <p>The following method reduces the problem to the known case $p=1$.</p> <p>Notice that $P_Z \equiv ZZ^t$ is an orthogonal projector of rank $p$, thus:</p> <p>$\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)$</p> <p>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$.</p> <p>Denote by $\rho(A)$ the completely antisymmetric $p$-tensor product representation of $A$:</p> <p>$\rho(A) \circ v_1 \wedge . . . \wedge v_p = Av_1 \wedge . . . \wedge A v_p$</p> <p>We have:</p> <p>$\det( I_m + P_Z(A-I_m)P_Z) = \mbox{tr} (\rho(P_Z) \rho(A))$</p> <p>(Both sides are equal, because they are just the determinant of the restriction of A to the range of $P_Z$.</p> <p>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$.</p> http://mathoverflow.net/questions/57619/minimizing-determinantztranspose-a-z/57681#57681 Answer by Sergei Ivanov for Minimizing determinant(Ztranspose.A.Z) Sergei Ivanov 2011-03-07T14:54:12Z 2011-03-07T15:36:00Z <p>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$. <strong>Update:</strong> This fact is well-known as <a href="http://en.wikipedia.org/wiki/Min-max_theorem#Cauchy_interlacing_theorem" rel="nofollow">Cauchy interlacing theorem</a>.</p> <p><strong>Proof.</strong> 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$.</p> <p>Suppose that $\mu_k&lt;\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 &lt;\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.</p> <p>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.</p>