5

Say $A$ is a submatrix of $B$. How do I prove that the $\|A\|_2 \leq \|B\|_2$? I can easily show this for $\|\cdot\|_1, \|\cdot\|_\infty, $ and $\|\cdot\|_F$ and thought maybe the solution lies in relating the inequalities of these other norms to the 2-norm, but this path hasn't proved fruitful.

sfTurpin1990
  • 85
  • Can you clarify which meaning of a "submatrix" you are using? My inclination is to assume that you are working with the definition found here: http://mathworld.wolfram.com/Submatrix.html. But there are more general ways to talk about submatrices. – Xoque55 Nov 11 '15 at 19:18
  • The actual case I am working with is the principal submatrix (so if $B \in n \times n$ then $A$ is the upper left submatrix of size $n-1 \times n-1$). However, I believe this holds for any submatrix as defined in the reference you posted. – sfTurpin1990 Nov 11 '15 at 19:24
  • Are you familiar with how the 2-norm relates to the spectral radius of a matrix? That is, do you know why the 2-norm is also known as the spectral norm? – Xoque55 Nov 11 '15 at 19:31
  • I am, but how can I show that the spectral radius of the submatrix is less than the original? – sfTurpin1990 Nov 11 '15 at 19:36

4 Answers4

2

In my opinion, the standard definition of the of the 2-norm of a matrix is enough to prove the above theorem. Consider a matrix, $A$ and it's submatrix $B$. Let the value of the term $||Bx||_2$ be maximum for a unit vector $z$. Then we can create a vector $m$ which has the elements of $z$ at the positions corresponding to the positions of the columns of $B$ in the matrix $A$ and rest of the elements in $m$ are zeros. This also ensures that $m$ is a unit norm vector. Then it is easy to see that the value of $||Am||_2$ is greater than or equal to the value of $||Bz||_2$. This means that the maximum value of $||Ax||_2$ is greater than or equal to the maximum value of $||Bx||_2$ which basically means that $||A||_2$ is greater than or equal to $||B||_2$.

Hope this helps.

anubhav saikia
  • 21
1

COMMENT.-Your vectorial space is of dimension $mn$ if the matrix $B$ is $m$ x $n$ and the corresponding $2$-norm is given by$||B||=\sqrt{|a_{11}|^2+|a_{12}|^2+......+|a_{mn}|^2}$ .On the other hand all submatrix $A$ of $B$ has a norm in which some terms $a_{ij}$ of the norm of $B$ are equal and the other are zero. The inequality is clear.

Piquito
  • 29,594
  • But that is how one computes the Frobenius norm, not the 2-norm! – Xoque55 Nov 11 '15 at 19:22
  • 1
    @Ataulfo The definition of the 2-norm of a matrix is $$\sup_{|x|_2 = 1} |Ax|_2$$ – sfTurpin1990 Nov 11 '15 at 19:26
  • This is the norm of the linear operator defined by the matrix respect of a FIXED base. This norm is independent of any base. But the matrix change if you change of base. It is maybe a convention distinct of what I know. (for example, in France there are fields commutative and non commutative and a compact is always separated which is not the case in USA). Regards. – Piquito Nov 11 '15 at 23:50
1

Without loss of generality, let $B=\pmatrix{A&X\\ Y&Z}$. Then \begin{aligned} \|A\|_2 &=\sup_{\|x\|_2=1}\|Ax\|_2\\ &\le\sup_{\|x\|_2=1}\left\|\pmatrix{A\\ Y}x\right\|_2\\ &=\sup_{\|x\|_2=1}\left\|B\pmatrix{x\\ 0}\right\|_2\\ &\le\sup_{\|u\|_2=1}\left\|Bu\right\|_2\\ &=\|B\|_2. \end{aligned} In particular, if $Y$ has full column rank, then $Yx\ne0$; hence the first inequality above is strict and $\|A\|_2<\|B\|_2$. Since the induced $2$-norm of a matrix $M$ is also equal to $\sup_{\|y\|_2=1}\|y^\ast M\|_2$, we also have $\|A\|_2<\|B\|_2$ when $X$ has full row rank.

user1551
  • 139,064
0

Let $\boldsymbol{B}=\boldsymbol{R}_{0}\boldsymbol{A}\boldsymbol{C}_{0}$, where $\boldsymbol{R}_{0},\boldsymbol{C}_{0}$ are the identity matrices with $1$'s replaced by $0$'s at positions of the removed rows and columns. We have \begin{align*} \|\boldsymbol{B}\|_{2}^{2} & \triangleq\max\limits _{\boldsymbol{x},\,\|\boldsymbol{x}\|=1}\|\boldsymbol{R}_{0}\boldsymbol{A}\boldsymbol{C}_{0}\boldsymbol{x}\|_{2}^{2}=\max\limits _{\boldsymbol{y},\,\|\boldsymbol{y}\|=1}\quad\max\limits _{\boldsymbol{x},\,\|\boldsymbol{x}\|=1}\left(\boldsymbol{y}^{T}\boldsymbol{R}_{0}\boldsymbol{A}\boldsymbol{C}_{0}\boldsymbol{x}\right)^{2}\\ & =\max\limits _{\boldsymbol{y},\,\|\boldsymbol{y}\|=1,\,\boldsymbol{y}\in\mathcal{C}(\boldsymbol{R}_{0}^{T})}\quad\max\limits _{\boldsymbol{x},\,\|\boldsymbol{x}\|=1,\,\boldsymbol{x}\in\mathcal{C}(\boldsymbol{C}_{0})}\left(\boldsymbol{y}^{T}\boldsymbol{A}\boldsymbol{x}\right)^{2}\\ & \leq\max\limits _{\boldsymbol{y},\,\|\boldsymbol{y}\|=1}\max\limits _{\boldsymbol{x},\,\|\boldsymbol{x}\|=1}\|\boldsymbol{y}^{T}\boldsymbol{A}\boldsymbol{x}\|_{2}^{2}=\|\boldsymbol{A}\|_{2}^{2}, \end{align*} where $\mathcal{C}(\boldsymbol{C}_{0})\equiv\mathrm{Im}\boldsymbol{C}_{0}$ denotes the column space of the matrix.

The transition to the second line can be figured out as follows: if $\boldsymbol x$ has a non-zero component in the null-space $\boldsymbol{C}_{0}$, then the objective can be improved at the expense of this component; therefore, an optimum is in $\mathcal{C}(\boldsymbol{C}_{0})$. A similar argument applies to $\boldsymbol{y}$.

The transition to the third line is due that the fact that removing the constraints $\boldsymbol{x}\in\mathcal{C}(\boldsymbol{C}_{0})$ and $\boldsymbol{y}\in\mathcal{C}(\boldsymbol{R}_{0}^{T})$ can only improve the optimum. As we are maximising here, the inequality sign is $\leq$.

I guess, another way to prove the inequality is by considering the singular value decomposition of the matrix (as a sum of outer products) and making essentially the same argument there.

Update. See also a sketch of a proof relying on submultiplicativity, which holds for induced matrix norms: https://www.physicsforums.com/threads/proof-that-norm-of-submatrix-must-be-less-than-norm-of-matrix-its-embedded-in.436855/

paperskilltrees
  • 692