Maximize $\det(W^*DW)$, where $D$ is real diagonal

eigenvalues-eigenvectorslinear algebraoptimization

Suppose $D$ is a diagonal matrix, $D=\textrm{diag}(d_1, d_2, \cdots, d_n)$ with $d_1> d_2 > \cdots > d_n\ge 0$. Let $W=[\pmb{w_1}, \pmb{w_2}, \cdots, \pmb{w_m} ]$ be a $n\times m$ matrix ($m\le n$) whose columns are each of unit norm, i.e. $\Vert\pmb{w_i}\Vert=1$. What $W$ maximizes $\det(W^*DW)$?

For $m=1$, clearly any eigenvector of $D$ corresponding to eigenvalue $d_1$ will do. E.g. $W=e_1\triangleq [1\,0\cdots0]^T$, and $\det(W^*DW)=d_1$.

What about $m\ge2$? Any $W$ whose columns consist of normalized eigenvectors of $D$ corresponding to the $m$ largest eigenvalues of $D$? How to prove it?

Best Answer

Note $\det(W^*DW)\geq 0$ since $W^*DW\succeq \mathbf 0$ and that all $m$ columns of $W$ should be selected to be linearly independent, otherwise we get a determinant of zero which can only be a maximum in the trivial case of $d_n=0$ and $n=m$ (and any choice of $W$ is a maximum in such a case).

Since $W$ is injective, run 'thin' QR factorization $W=QR$ there $R$ is invertible and $Q$ is tall and skinny. (Recall this means that $Q$ has orthonormal columns and $R$ has positive diagonal elements.)

$\det\big(W^*DW\big)= \det\big(R^*Q^*DQR\big)= \det\big(R^*\big)\cdot \det\big(Q^*DQ\big)\cdot \det\big(R\big)$
$\leq \det\big(Q^*DQ\big)$
$ \leq \prod_{k=1}^m d_k$

where the inequalities are
(i) $\det\big(R\big) \leq 1$ since $\big \Vert \mathbf w_i\big \Vert_2 =1$ implies each column of $R$ has length one, hence its diagonal elements (which are positive) are at most one but $R$ is triangular so its determinant is given by the product of its diagonal.
(ii) recognizing that the determinant is the product of the eigenvalues of a matrix, apply Cauchy Interlacing to $Q^*DQ$ to see that its kth largest eigenvalue observes $0\leq \lambda_k \leq d_k$ and multiply over the bound.

Conclude:
in the maximizing case $R = I$ and so $W$ has orthonormal columns which should be given by standard basis vectors