3
$\begingroup$

I have the following exercise:

Relate the 2-norm condition of $X\in \Bbb R^{m\times n}\ (m\geq n)$ to the 2-norm condition of the matrices: $$B=\begin{equation} \begin{bmatrix} I_m & X\\ 0 & I_n \end{bmatrix} \end{equation}$$ and $$C=\begin{equation} \begin{bmatrix} X\\ I_n \end{bmatrix} \end{equation} $$

My attemp:

We know that the condition number of a matrix for the 2-norm is given by the following expression: $$\kappa_2(A)=||A||_2 ||A^{-1}||_2$$

Also I have a property that says if $B$ is a submatrix of $A$ then

$$||B||_2\leq ||A||_2$$

So using this I have:

$$\kappa_2(B)=||B||_2 ||B^{-1}||_2\geq ||X||_2||X^{-1}||_2=\kappa_2(X)$$ But I am not sure that it is necessarily true that if $X$ is a submatrix of $B$ then necessarily $ X^{-1} $ is a submatrix of $B^{-1}$

If this works then for the $ C $ it would be worth the same, but doing numerical experiments this fails, numerically I get: $$\kappa_2(C)\leq \kappa_2(X) \leq \kappa_2(B)$$

I appreciate any help you can give me, regards

Edit:

I have seen that $X$ is not square so the inverse does not exist and therefore kappa will not exist either. For this, in Golub's book it is said that it can also be calculated as the maximum singular value between the minimum singular value, that is: $$\kappa_2(A)=\dfrac{\sigma_{max}}{\sigma_{min}}$$ And in this case, as the matrix $X$ is given, for any matrix the 2-norm condition can be obtained, applying the singular value decomposition theorem

$\endgroup$

2 Answers 2

1
+50
$\begingroup$

$$C=\begin{bmatrix} X \\ I_n\end{bmatrix}$$

$$C^TC=X^TX+I$$

Hence $$\lambda_{\max}(C^TC)=\lambda_{\max}(X^TX)+1$$ $$\lambda_{\min}(C^TC)=\lambda_{\min}(X^TX)+1$$

That is $$\kappa(C)=\frac{\sigma_{\max}(C)}{\sigma_{\min}(C)}=\sqrt{\frac{\lambda_{\max}(X^TX)+1}{\lambda_{\min}(X^TX)+1}}\le \sqrt{\frac{\lambda_{\max}(X^TX)}{\lambda_{\min}(X^TX)}}=\kappa(X)$$

$\endgroup$
2
  • $\begingroup$ Thank you very much, is the relation between C and X correct as I got it? $\endgroup$
    – Haus
    Apr 28, 2021 at 18:36
  • $\begingroup$ it's a possible correct relation. $\endgroup$ Apr 29, 2021 at 2:22
1
$\begingroup$

This is still a partial answer.

For $B$, the inverse is given by $$B^{-1}=\begin{pmatrix}\mathbb{I}_m & -X\\ 0 & \mathbb{I}_n \end{pmatrix}$$ Now let us see what is the operator norm of $B$ and $B^{-1}$ respectively. $$||B||_2=\sup_{||\textbf{u}||_2=1}(\textbf{u}_1^T, \textbf{u}_2^T)\begin{pmatrix}\mathbb{I}_m & X\\ 0 & \mathbb{I}_n \end{pmatrix} \begin{pmatrix}\textbf{u}_1\\ \textbf{u}_2\end{pmatrix}$$ $$=\sin^2\theta+\cos^2\theta+\sin\theta\cos\theta\hat{\textbf{u}}_1^TX\hat{\textbf{u}}_2$$ $$=1+\frac{||X||_2}{2}=||B^{-1}||_2$$ Therefore $$\kappa(B)=\Big(1+\frac{||X||_2}{2}\Big)^2$$

$\endgroup$
1
  • $\begingroup$ Hello, thank you very much for contributing. I have asked my teacher and it may be in terms of inequalities, but with this that you mention it is verified that $\kappa (B)\geq\kappa (X)$. To relate to $C$, I conjecture that $\kappa(X)\geq \kappa(C)$, we know from the alternate definition that we are interested in the singular values ​​of $C$, so we can see that $X^{*}X + I_n= C$ so from here it follows that $\sigma_{max}(C)\geq \sigma_{max}(X) \text{ and } \sigma_{min}(C)\geq \sigma_{min}(X)$. But I don't know how to conclude, that has been another advance. (I also tried to use the SVD) $\endgroup$
    – Haus
    Apr 25, 2021 at 7:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .