# A singular value inequality for nonnegative matrices

This post concerns a question regarding nonnegative matrices, i.e., matrices with all entries nonnegative:

For two nonnegative matrices ${A,B \in {\mathbb R}^{m\times n}}$, if ${A-B\geq 0}$, i.e., ${A-B}$ is nonnegative as well, is there any relation with their singular values?

As we shall see, indeed, the largest singular value of ${A}$, denoted as ${\sigma_1(A)}$, is larger than the largest singular value of ${B}$, ${\sigma_1(B)}$:

$\displaystyle \sigma_1(A)\geq \sigma_1(B).$

Let us first consider a simpler case when ${A,B\in {\mathbb R}^{n\times n}}$ are symmetric, so that ${\sigma_1(A)=\max\{|\lambda_1(A)|,|\lambda_n(A)|\}}$, ${\sigma_1(B) =\{|\lambda_1(A)|,|\lambda_n(B)|\}}$. Here for any symmetric matrix ${C}$, we denote its eigenvalues as ${\lambda_1(C)\geq \dots \geq \lambda_n(C)}$.

Lemma 1
If ${A,B,A-B\in {\mathbb R}^{n\times n}}$ are all nonnegative and symmetric, then

$\displaystyle \sigma_1(A)\geq \sigma_1(B).$

Proof:
To prove the lemma, we first recall the Perron-Frobenius theorem which states that the largest eigenvalue (in magnitude) of a
nonnegative matrix is nonnegative and the eigenvalue admits an eigenvector which is entrywise nonnegative as well.

Using this theorem, we can pick a nonnegative unit norm eigenvector ${v_B}$ corresponding to the eigenvalue ${\lambda_1(B)}$, which is both nonnegative and largest in magnitude. Next, by multiplying left and right of ${A-B}$ by ${v_B^\top}$ and ${v_B}$ respectively, we have

$\displaystyle 0\overset{(a)}{\leq} v_B^\top Av_B - v_B^\top Bv_B \overset{(b)}{=} v_B^\top Av_B-\lambda_1(B)\overset{(c)}{\leq} \lambda_1(A)-\lambda_1(B)\overset{(d)}{=}\sigma_1(A)-\sigma_1(B).$

Here step ${(a)}$ is because ${A-B}$ is nonnegative and ${v_B}$ is nonnegative.
The step ${(b)}$ is because ${v_B}$ has unit norm and ${Bv_B =\lambda_1(B)v_B}$. The step ${(c)}$ is because ${\lambda_1(A) =\max_{\|v\|= 1}v^\top Av}$. The step ${(d)}$ is because ${A,B}$ are symmetric and both are nonnegative so largest eigenvalue is indeed just the singular value due to Perron-Frobenius theorem. $\Box$

To prove the general rectangular case, we use a dilation argument.

Theorem 2
If ${A,B,A-B\in {\mathbb R}^{m\times n}}$ are all nonnegative, then

$\displaystyle \sigma_1(A)\geq \sigma_1(B).$

Proof:
Consider the symmetric matrices ${\tilde{A}}$ and ${\tilde{B}}$ in ${{\mathbb R}^{(n+m)\times (n+m)}}$:

$\displaystyle \tilde{A} = \begin{bmatrix} 0 & A \\ A^\top & 0 \end{bmatrix},\quad \text{and} \quad \tilde{B} = \begin{bmatrix} 0 & B \\ B^\top & 0 \end{bmatrix}.$

Note that ${\tilde{A}}$ has the largest singular value as ${A}$ and ${\tilde{B}}$ has the largest singular value as ${B}$.
Now since ${A,B,A-B\geq 0}$, we also have ${\tilde{A},\tilde{B},\tilde{A}-\tilde{B}\geq 0}$. Using Lemma 1, we prove the theorem.
$\Box$

How about the second singular value of ${A}$ and ${B}$? We don’t have ${\sigma_2(A)\geq \sigma_2(B)}$ in this case by considering

$\displaystyle A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.$