share
MathematicsHow to prove the following matrix is negative semi-definite matrix using Weyl's eigenvalue inequality and Rayleigh quotient?
[0] [1] chloe
[2022-01-25 15:16:31]
[ matrices eigenvalues-eigenvectors ]
[ https://math.stackexchange.com/questions/4365830/how-to-prove-the-following-matrix-is-negative-semi-definite-matrix-using-weyls ]

Given a negative semi-definite matrix $A=\{a_{ij}\}_{i,j\in\{1,2,...,n\}}$, how to prove the following two matrices are still a negative semi-definite, using Weyl's eigenvalue inequality and the concept of Rayleigh quotient?

The first matrix:

$\left[ \begin{array}{ccccc|c} a_{1,1}&a_{1,2}&\cdots&a_{1,n-1}&a_{1,n}&0\\ a_{2,1}&a_{2,2}&\cdots&a_{2,n-1}&a_{2,n}&0\\ \vdots&\ddots&\ddots&\vdots&\vdots&\vdots\\ a_{n-1,1}&a_{n-1,2}&\cdots&a_{n-1,n-1}&a_{n-1,n}&0\\ a_{n,1}&a_{n,2}&\cdots&a_{n-1,n}&a_{n,n}\color{red}{-1} &\color{red}{1}\\ \hline 0 &0 &\cdots&0&\color{red}{1} &\color{red}{-1} \end{array} \right] $

The second matrix:

$\left[ \begin{array}{ccccc|c} a_{1,1}&a_{1,2}&\cdots&a_{1,n-1}&a_{1,n}&0\\ a_{2,1}&a_{2,2}&\cdots&a_{2,n-1}&a_{2,n}&0\\ \vdots&\ddots&\ddots&\vdots&\vdots&\vdots\\ a_{n-1,1}&a_{n-1,2}&\cdots&a_{n-1,n-1}&a_{n-1,n}&0\\ a_{n,1}&a_{n,2}&\cdots&a_{n-1,n}&a_{n,n}\color{red}{+1}&\color{red}{-1}\\ \hline 0 &0 &\cdots&0&\color{red}{-1} &\color{red}{1} \end{array} \right] $

The first matrix is negative semidefinite because the sum of negative semidefinite matrices must be negative semidefinite. The second matrix might not be negative semidefinite. - Ben Grossmann
@BenGrossmann Thank you. The second matrix is actually also negative semi-definite, but I don't know how to prove it. - chloe
(1) In fact, the second matrix cannot possibly be negative semidefinite: if we take $x = (0,\dots,0,1)^T$, then $x^TMx > 0$. Why do you believe that the matrix is negative semidefinite? - Ben Grossmann
@BenGrossmann I re-checked, yes, the second one is not $\leq 0$. Is it possible to prove the first one using Weyl's eigenvalue inequality and the concept of Rayleigh quotient? Maybe this makes things complicated but just want to understand something in the paper.. - chloe
[+2] [2022-01-25 16:22:49] Ben Grossmann [ACCEPTED]

We can prove that the first matrix is negative semidefinite as follows. Note that the matrix can be expressed as $M = A + B$, where $$ A = \left[ \begin{array}{ccccc|c} a_{1,1}&a_{1,2}&\cdots&a_{1,n-1}&a_{1,n}&0\\ a_{2,1}&a_{2,2}&\cdots&a_{2,n-1}&a_{2,n}&0\\ \vdots&\cdots&\ddots&\vdots&\vdots&\vdots\\ a_{n-1,1}&a_{n-1,2}&\cdots&a_{n-1,n-1}&a_{n-1,n}&0\\ a_{n,1}&a_{n,2}&\cdots&a_{n-1,n}&a_{n,n}&0\\ \hline 0 &0 &\cdots&0&0 &0 \end{array} \right],\\ B = \left[ \begin{array}{ccccc|c} 0&0&\cdots&0&0&0\\ 0&0&\cdots&0&0&0\\ \vdots&\cdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&\cdots&0&0&0\\ 0&0&\cdots&0&-1&1\\ \hline 0 &0 &\cdots&0&1 &-1 \end{array} \right]. $$ It is clear that these matrices are negative semidefinite. With the Rayleigh quotient, we can see that $$ \begin{align*} \lambda_{\max}(A + B) &= \max_{x \neq 0} \frac{x^T(A + B)x}{x^Tx} = \max_{x \neq 0} \frac{x^TAx}{x^Tx} + \frac{x^TBx}{x^Tx} \\ &= \max_{x \neq 0, y \neq 0, x = y} \frac{x^TAx}{x^Tx} + \frac{y^TBy}{y^Ty} \\ & \leq \max_{x \neq 0, y \neq 0} \frac{x^TAx}{x^Tx} + \frac{y^TBy}{y^Ty} \\ & = \max_{x \neq 0}\frac{x^TAx}{x^Tx} + \max_{y \neq 0} \frac{y^TBy}{y^Ty} = \lambda_{\max}(A) + \lambda_{\max}(B) \leq 0 + 0 = 0. \end{align*} $$ So, $A + B$ is indeed symmetric with non-positive eigenvalues.

That said, there's no need to invoke the Rayleigh quotient: for the definition of negative semidefinite, we need to show that $x^T(A + B)x \leq 0$ for all $x$. With that, merely note that for all $x$, we have $$ x^T(A + B)x = x^TAx + x^TBx \leq 0 + 0 = 0, $$ where we use the fact that $A$ and $B$ are negative semidefinite.


1