Weighted sum of diagonal values is dominated by the sum of the singular values

inequalitymatrix-calculusmultivariable-calculusoptimizationsvd

Let $A$ be a $2 \times 2$ real matrix with $\det A \ge 0$, and let $\sigma_1 \le \sigma_2$ be its singular values. Let $0 \le x_1 \le x_2$. How to prove that $x_1 A_{11} +x_2A_{22} \le x_1 \sigma_1+x_2 \sigma_2$?

I have a proof, but it uses Riemannian geometry. I am looking for a more elementary proof.

Equivalent formulation:

Set $K=\{ A \in M_2 \, | \, \det A \ge 0 \, \, \text{ and the singular values of } A \, \text{are } \sigma_1,\sigma_2 \}$. Then
$$\max_{A \in K} x_1 A_{11} +x_2A_{22}=x_1 \sigma_1+x_2 \sigma_2.$$

It suffices to prove that the maximum is obtained at a diagonal matrix; for a diagonal matrix with nonnegative entries $A=\operatorname{diag}(\sigma_{\alpha(i)})$, the claim reduces to the rearrangement inequality
$\sum_i x_i\sigma_{\alpha(i)} \le \sum_i x_i\sigma_i$, where $\alpha \in S_2$ is a permutation.(for dimension $2$ this can be verified directly by hand.)

I guess this should be well-known. Is there any reference in the literature?
Is it true for $n \times n$ matrices?

If $x_1=x_2$, then this reduces to $\text{tr}(A) \le \sigma_1+\sigma_2$ which is a classic easy result.

Best Answer

Yes this is true irrespective of the determinant of $A$ or dimension $n$. (I normally write singular values in the opposite order with $\sigma_1$ being largest but I'll try your notation)

$X:=diag(\mathbf x)$ i.e. a diagonal matrix with $x_{i,i} := x_i$ so $X\succeq \mathbf 0$. And let $\Sigma_A$ have the singular values of $A$ in your ordering.

$\sum_{k=1}^n a_{k,k}\cdot x_k = \text{trace}\Big(AX\Big)\leq \text{trace}\Big(\Sigma_A X\Big)= \sum_{k=1}^n \sigma_{k}\cdot x_k$
by the von Neumann Trace Inequality

Related Solutions

Is this condition on the eigenvalues of a matrix rigid under orthogonal multiplication

I assume $\sigma_1\neq 0$, which means that $\Sigma$ is invertible. Let $A=Q\Sigma^{-1}.$ Then $Q=A\Sigma$ and $Q^T=\Sigma A^T.$

We want $Q^T \Sigma$ to be symmetric, which means $Q^T\Sigma = \Sigma Q$ or $\Sigma A^T \Sigma = \Sigma A\Sigma.$ If we multiply this with $\Sigma^{-1}$ from both sides, we get $A=A^T,$ so $A$ is symmetric.

$Q$ is orthogonal, which means $Q^TQ=I$ or $$ \Sigma A^2 \Sigma = I $$ or $$ A^2 = \Sigma^{-2} $$ So we are looking for a square root of $\Sigma^{-2}$ and the problem boils down to the question if $\Sigma^{-1}$ is the only valid choice.

We must consider the case that $\Sigma$ has eigenvalues with multiplicity of more than $1.$

Let $\sigma_{r_i} = \sigma_{r_i+1} = \ldots = \sigma_{r_{i+1}-1}$ for $i=1,\ldots,m$ and $r_1=1,$ $r_2=2$ and $r_{m+1}=n+1.$ Furthermore, $\sigma_{r_i}<\sigma_{r_{i+1}}$ for $i=1,\ldots,m-1.$ Then each square root of $\Sigma^{-2}$ can be written as follows $$ A = \begin{pmatrix} \sigma_{r_1}^{-1} B_1 & & & & 0 \\ & \sigma_{r_2}^{-1} B_2 & & & \\ & & \sigma_{r_3}^{-1} B_3 & & \\ & & & \ddots & \\ 0 & & & & \sigma_{r_m}^{-1} B_m \end{pmatrix} \;\;,\;\; B_i^2 = I\;\;\mbox{for}\;\; i=1,\ldots,m $$ where $B_i$ are blocks of size $(r_{i+1}-r_i)\times (r_{i+1}-r_i).$ (The proof is given below)

Then $$ Q = \begin{pmatrix} B_1 & & & & 0 \\ & B_2 & & & \\ & & B_3 & & \\ & & & \ddots & \\ 0 & & & & B_m \end{pmatrix} $$ The $B_i$ are symmetric. $B_i^T$ is the inverse of $B_i$ because of the orthogonality of $Q$, and $B_i$ is also the inverse of $B_i$, because of the property $B_i^2=I.$ Therefore $B_i^T=B_i$ and $$ Q^T\Sigma = \begin{pmatrix} \sigma_{r_1}B_1 & & & & 0 \\ & \sigma_{r_2}B_2 & & & \\ & & \sigma_{r_3}B_3 & & \\ & & & \ddots & \\ 0 & & & & \sigma_{r_m}B_m \end{pmatrix} $$ We want $Q^T\Sigma$ to have the same eigenvalues as $\Sigma,$ which in turn means that $\sigma_{r_i}B_i$ has $\sigma_{r_i}$ as its only eigenvalue. A symmetric matrix with only one eigenvalue must be a scalar multiple of the identity matrix. Therefore, $B_i = I$ for $i,\ldots,m,$ which completes the proof.

Proof sketch for $\sigma_1=0$

If $\sigma_1=0,$ it can easily be shown that $Q_{11}\in\{-1,1\}$ and $Q_{1j}=Q_{j1}=0$ for $j=2,\ldots,n.$ This can be concluded from the symmetry of $Q^T\Sigma$ and from the orthogonality of $Q.$

This means that we can follow the argument from the first part of the proof, but consider only the subspace that is orthogonal to $e_1.$ Basically, this means that we ignore the first row and first column of all $n\times n$ matrices. In the end, we have to decide if $Q_{11}=1$ or $Q_{11}=-1.$ As $Q\in \mathrm{SO}(n)$ and $B_i=I$ for $i=2,\ldots,m,$ we can conclude $Q_{11}=1.$

Diagonalizable square roots of diagonal matrices

Let $A$ be diagonalizable and $A^2$ diagonal. Without loss of generality, the diagonal elements of $A^2$ are sorted in ascending order. Let $0\leq\lambda_1 < \lambda_2 < \ldots < \lambda_m$ such that the eigenvalues of $A$ form a (not necessarily strict) subset of $\{\lambda_1,\;-\lambda_1,\;\lambda_2,\;-\lambda_2,\;\ldots,\;\lambda_m,\;-\lambda_m\}.$ Let $t_i^{+}$ be the algebraic and geometric multiplicity of $\lambda_i$ and $t_i^{-}$ the algebraic and geometric multiplicity of $-\lambda_i$ within the matrix $A$ (we set $t_1^{-}=0$ if $\lambda_1=0.$) Let $r_1=1$ and $r_{i+1} = r_i + t_i^{+}+ t_i^{-}.$

If $Av = \lambda v$ and $Aw = -\lambda w,$ then $A^2 (v+w) = A^2 v + A^2 w =\lambda^2 v + (-\lambda)^2 w = \lambda^2 (v+w).$ This means that the eigenspace of $A^2$ with respect to the eigenvalue $\lambda^2$ is the direct sum of the eigenspaces of $A$ with respect to the eigenvalues $\lambda$ and $-\lambda.$

As $A$ is diagonalizable, the direct sum of the eigenspaces $E_{A,\lambda_1},$ $E_{A,-\lambda_1}$, $E_{A,\lambda_2},$ $E_{A,-\lambda_2},\ldots$, $E_{A,\lambda_m},$ $E_{A,-\lambda_m}$, forms the complete vector space $\mathbb{R}^n.$ This means that each of the eigenspaces of $A^2$ can be written as $E_{A,\lambda_i} \oplus E_{A,-\lambda_i}.$ In a manner of speaking, there is no room for other eigenspaces than those.

We know the eigenspaces of $A^2,$ because $A^2$ is diagonal. We have \begin{eqnarray*} E_{A^2,\lambda_1^2} & = & E_{A,\lambda_1} \oplus E_{A,-\lambda_1} = \mathrm{span}\{e_{r_1},\ldots,e_{r_2-1}\} \\ & \vdots & \\ E_{A^2,\lambda_m^2} & = & E_{A,\lambda_m} \oplus E_{A,-\lambda_m} = \mathrm{span}\{e_{r_m},\ldots,e_{r_{m+1}-1}\} \end{eqnarray*} with the standard basis $e_1,\ldots,e_n.$ Now it is clear that $A$ can be diagonalized by means of a block matrix, because each $E_{A,\lambda_i} \oplus E_{A,-\lambda_i}$ is spanned by the related elements of the standard basis. $$ A= \begin{pmatrix} S_1 & & 0 \\ & \ddots & \\ 0 & & S_m \end{pmatrix} \begin{pmatrix} \lambda_1 I_{t_1^{+}} & & & & 0 \\ & -\lambda_1 I_{t_1^{-}} & & & \\ & & \ddots & & \\ & & & \lambda_m I_{t_m^{+}} & \\ 0 & & & & -\lambda_m I_{t_m^{-}} \end{pmatrix} \begin{pmatrix} S_1 & & 0 \\ & \ddots & \\ 0 & & S_m \end{pmatrix} ^{-1} $$ From this, by simply processing the matrix multiplication, we can conclude that $A$ itself is also a block matrix of the same sort, i.e. $$ A = \begin{pmatrix} A_1 & & 0 \\ & \ddots & \\ 0 & & A_m \end{pmatrix} $$ with $$ A_i = S_i\,\begin{pmatrix} \lambda_i I_{t_i^{+}} & \\ & -\lambda_i I_{t_i^{-}} \\ \end{pmatrix} \, S_i^{-1} $$ Now we only have to show that $A_i = \lambda_i B_i$ with $B_i^2=I.$

Let $T_i=S_i^{-1}$.

Let $S_i^{+}$ be the $(t_i^{+}+t_i^{-})\times t_i^{+}$ matrix that is formed by the first $t_i^{+}$ columns of $S_i$ and $S_i^{-}$ the $(t_i^{+}+t_i^{-})\times t_i^{-}$ matrix that is formed by the last $t_i^{-}$ columns of $S_i.$ Let $T_i^{+}$ be the $t_i^{+}\times (t_i^{+}+t_i^{-})$ matrix that is formed by the first $t_i^{+}$ rows of $T_i$ and $T_i^{-}$ the $t_i^{-}\times (t_i^{+}+t_i^{-})$ matrix that is formed by the last $t_i^{-}$ rows of $T_i.$

Then $T_i^{+}S_i^{+}=I,\;\;T_i^{-}S_i^{-}=I,\;\;T_i^{+}S_i^{-}=0,\;\;T_i^{-}S_i^{+}=0$. $$ A_i = S_i^{+}\lambda_i T_i^{+} + S_i^{-}(-\lambda_i) T_i^{-} = \lambda_i \left( S_i^{+}T_i^{+} - S_i^{-}T_i^{-}\right) $$ Let $B_i = S_i^{+}T_i^{+} - S_i^{-}T_i^{-}.$ Then \begin{eqnarray*} B_i^2 & = & \left( S_i^{+}T_i^{+} - S_i^{-}T_i^{-}\right)\left( S_i^{+}T_i^{+} - S_i^{-}T_i^{-}\right) \\ & =& S_i^{+}T_i^{+}S_i^{+}T_i^{+}-S_i^{+}T_i^{+}S_i^{-}T_i^{-}-S_i^{-}T_i^{-}S_i^{+}T_i^{+}+S_i^{-}T_i^{-}S_i^{-}T_i^{-} \\ & =& S_i^{+}\cdot I\cdot T_i^{+}-S_i^{+}\cdot 0 \cdot T_i^{-}-S_i^{-}\cdot 0 \cdot T_i^{+}+S_i^{-}\cdot I\cdot T_i^{-} \\ & =& S_i^{+}T_i^{+}+S_i^{-}T_i^{-} \\ & =& \begin{pmatrix} & & \\ S_i^{+} & & S_i^{-} \\ & & \end{pmatrix} \begin{pmatrix} & T_i^{+} & \\ & & \\ & T_i^{-} & \end{pmatrix} =S_iT_i = I \end{eqnarray*}

Singular value decomposition in the language of operator theory

The singular value decomposition is obtained from the polar decomposition, together with the spectral theorem.

The polar decomposition gives you $A=V|A|$, where $V$ is a partial isometry such that $\operatorname{ran}V^*V=\overline{\operatorname{ran}A^*}$, and $|A|=(A^*A)^{1/2}$. Since $|A|\in B(H_1)$ and positive and compact, we apply the Spectral Theorem to obtain $$\tag1 |A|=\sum_{j=1}^\infty\sigma_j\,P_j, $$ where $\sigma_1\geq\sigma_2\geq\cdots\geq0$ and each $P_j$ is a rank-one projection. We can rewrite $(1)$ as $$\tag2 |A|=U^*DU, $$ where $U$ is a unitary and the is the diagonal operator (in the canonical basis, say) with diagonal $\sigma_1,\sigma_2,\ldots$

Then $$\tag3 A=VU^*DU=WDU $$ where $D$ is as above, $W$ is a partial isometry, and $U$ is unitary.

An often more useful way of writing this is choosing unit vectors $e_j$ with $P_je_j=e_j$ (so they form an orthonormal basis of the range of $|A|$) and write $(1)$ as $$\tag4 |A|=\sum_{k=1}^\infty\sigma_k\,\langle\cdot,e_k\rangle \,e_k. $$ Then $$\tag5 A=V|A|=\sum_{k=1}^\infty\sigma_k\,\langle\cdot,e_k\rangle \,Ve_k. $$ As $V$ is an isometry on $\operatorname{ran}|A|$, we get that $\{Ve_k\}$ is orthonormal. So the Singular Value Decomposition can be restated as saying

If $A\in L(H_1,H_2)$ is compact there exist orthonormal families $\{e_k\}\subset H_1$ and $\{f_k\}\subset H_2$ such that $$\tag6 A=\sum_{k=1}^\infty\sigma_k\,\langle\cdot,e_k\rangle \,f_k. $$

Best Answer

Related Solutions

Is this condition on the eigenvalues of a matrix rigid under orthogonal multiplication

Singular value decomposition in the language of operator theory

Related Question