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

7
$\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, 2022 at 6:23
  • $\begingroup$ How does eigenvalue interlacing apply to $Q^*DQ$? Usually it applies to a principal submatrix. $\endgroup$
    – copper.hat
    Jul 11, 2022 at 5:33
  • 3
    $\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, 2022 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, 2022 at 5:57
  • $\begingroup$ @RyszardSzwarc That's another way. Thanks. $\endgroup$
    – River Li
    Jul 7, 2022 at 5:59
  • $\begingroup$ @user8675309 Thanks for your suggestion regarding the use of more appropriate theorems. $\endgroup$
    – River Li
    Jul 12, 2022 at 22:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .