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}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s