3
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Cool. I appreciate it. One minor clarification: Obviously $W$ is not unique. e.g. any $\pmb{w_i}=\alpha\cdot e_i,$ with $|\alpha|=1$ will do. $\endgroup$
    – syeh_106
    Jul 6 at 6:23
  • $\begingroup$ How does eigenvalue interlacing apply to $Q^*DQ$? Usually it applies to a principal submatrix. $\endgroup$
    – copper.hat
    Jul 11 at 5:33
  • 2
    $\begingroup$ @copper.hat Cauchy Interlacing merely requires $Q^*Q = I_m$. What you are stating is a special case of Interlacing, though one formulation implies the other. E.g. for your statement select $V\in U_n(\mathbb C)$ (i.e. $V^{-1}=V^*$) such that the first $m$ columns agree with $Q$, i.e. $Q=VS$ where $S$ is tall and skinny and $\mathbf s_j = \mathbf e_j$ (std basis vector). So $Q^*DQ=S^*V^*DVS=S^*\big(V^*DV\big)S$ and $\big(V^*DV\big)$ is hermitian and similar to $D$, so apply your interlacing statement to the leading $m\times m$ principle submatrix given by $S^*\big(V^*DV\big)S$ $\endgroup$ Jul 11 at 15:57
3
$\begingroup$

Alternative solution:

For a matrix $A \in \mathbb{C}^{n\times n}$ whose eigenvalues are all real, denote by $\lambda_1(A) \ge \lambda_2(A) \ge \cdots \ge \lambda_n(A)$ its eigenvalues.

We have \begin{align*} \det(W^\ast D W) &= \prod_{k=1}^m \lambda_k (W^\ast D W) \\ &= \prod_{k=1}^m \lambda_k (DWW^\ast) \tag{1}\\ &\le \prod_{k=1}^m \lambda_k (D) \cdot \prod_{k=1}^m \lambda_k(WW^\ast) \tag{2}\\ &= \prod_{k=1}^m d_k \cdot \prod_{k=1}^m \lambda_k(W^\ast W) \\ &\le \prod_{k=1}^m d_k \cdot \left(\frac{\sum_{k=1}^m \lambda_k(W^\ast W)}{m}\right)^m \tag{3}\\ &= \prod_{k=1}^m d_k \cdot \left(\frac{\mathrm{tr}(W^\ast W)}{m}\right)^m \\ &= \prod_{k=1}^m d_k. \tag{4} \end{align*} Explanations:
(1): All non-zero eigenvalues (counting algebraic multiplicity) of $AB$ and $BA$ are the same.
(2): Theorem H.1. in (Page 338, [1]).
(3): AM-GM inequality.
(4): $\mathrm{tr}(W^\ast W) = m$.

Also, when $W$ has orthonormal columns, we have $\det(W^\ast D W) = \prod_{k=1}^m d_k$.

Thus, the maximum of $\det(W^\ast D W)$ is $\prod_{k=1}^m d_k$.

Reference.

[1] A. W. Marshall, I. Olkin, and B. Arnold, “Inequalities: Theory of Majorization and Its Applications,” 2011.

$\endgroup$
3
  • $\begingroup$ Nice. $W^•W$ is a Gram matrix of vectors with length $1.$ So its determinant is less or equal $1.$ $\endgroup$ Jul 7 at 5:57
  • $\begingroup$ @RyszardSzwarc That's another way. Thanks. $\endgroup$
    – River Li
    Jul 7 at 5:59
  • $\begingroup$ @user8675309 Thanks for your suggestion regarding the use of more appropriate theorems. $\endgroup$
    – River Li
    Jul 12 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.