1
$\begingroup$

I know singular value decomposition of a matrix $A$ is $A=U\Sigma(V^T)$. And if we find to $x$ in $Ax=b$ we can use $A=U\Sigma V^T$ to get $x=V\Sigma'(U^T)b$.

But could somebody explain why $\Sigma$ in the SVD of $A$ is invertible?

$\endgroup$
4
  • 2
    $\begingroup$ Why do you think $\Sigma$ is invertible? Can you give more context? $\endgroup$
    – user856
    May 25, 2019 at 13:39
  • 2
    $\begingroup$ It is simply false to say "$\Sigma$ in the SVD of $A$ is invertible": think about the case when $A$ is the zero matrix. Take a look at Moore–Penrose inverse. $\endgroup$
    – user9464
    May 25, 2019 at 13:45
  • 1
    $\begingroup$ Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For typesetting, please use MathJax. $\endgroup$
    – dantopa
    May 25, 2019 at 20:49
  • $\begingroup$ Assuming $A$ is full rank and square then $\Sigma$ is simply a diagonal matrix whose inverse $\Sigma^{-1} = \frac{1}{\sigma_{i}}$ $\endgroup$
    – user3417
    May 25, 2019 at 23:20

3 Answers 3

1
$\begingroup$

This is one of those questions that depends on precise definitions, and is made harder to answer because it is a multipart question.

On the first part, about the SVD.

According to Wikipedia's definition, an $m\times n$ dimensional matrix $A$ has a factorization $A=U\Sigma V'$ (in the real case) where the dimensions of the factors are $m\times m$, $m\times n$, and $n\times n$ respectively, with $U$ and $V$ orthogonal. and $\Sigma$ "rectangular diagonal", with non-negative entries. According to this definition, the OP's premise that $\Sigma$ is invertible is false. As Jack commented, the zero matrix gives is a counterexample.

There is another definition of the SVD, in which the dimensions of the three factors are $m\times r$, $r\times r$, and $r\times n$, where $r$ is the rank of $A$. According to this definition, $\Sigma$ is invertible if $r>0$, that is, if $A$ is not the zero matrix. Here the intuition is, if $\Sigma$ had a zero diagonal element we miscalculated the rank $r$, and we should just strike the corresponding columns of $U$ and $V$ from the decomposition.

So, depending on the definition one uses, the answer to the OP's title question is either: no, it's not necessarily invertible, or it's invertible by definition.

Once one has settled on a clearer understanding of just what is meant by SVD, one can then go on to use it to help solve linear equations in various full rank and rank deficient situations. The OP's second sentence is also unclear about the assumptions and precise question his $Ax=b$ equation (is it for some $b$ or for any $b$, or what), and I am unable to reliably guess what he is actually after.

$\endgroup$
1
$\begingroup$

Executive summary

Given a matrix $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$, the $\Sigma$ matrix is a sabot matrix which pads $\mathbf{S}_{\rho \times \rho}$, the diagonal matrix of singular values, with 0 entries to insure conformability.

$$ \Sigma = \begin{bmatrix} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \\ \end{bmatrix}_{m\times n} \qquad \implies \qquad \Sigma^{\dagger} = \begin{bmatrix} \mathbf{S}^{-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \\ \end{bmatrix}_{n\times m} $$ You have locked onto a confusing issue. The quantity $\Sigma^{\dagger}$ means "invert the $\mathbf{S}$ matrix and pad with zero entries so the final shape is $n\times m$". Details follow.

Singular value decomposition

Begin with a nonzero matrix $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$ such that the matrix rank $\rho<m$ and $\rho<n$. The singular value decomposition, guaranteed to exist, is $$ \mathbf{A} = \mathbf{U} \, \Sigma \, \mathbf{V}^{*} = \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % \left[ \begin{array}{c} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right]. $$ Details of constructing the SVD can be found here and here.

The Moore-Penrose pseudoinverse is constructed according to $$ \mathbf{A}^{\dagger} = \mathbf{V} \, \Sigma^{\dagger} \, \mathbf{U}^{*} = % \left[ \begin{array}{cc} \color{blue}{\mathbf{V}_{\mathcal{R}\left(\mathbf{A}^{*}\right)}} & \color{red} {\mathbf{V}_{\mathcal{N}\left(\mathbf{A}\right)}} \end{array} \right] % \left[ \begin{array}{cc} \mathbf{S}^{-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}\left(\mathbf{A}\right)}} & \color{red} {\mathbf{U}_{\mathcal{N}\left(\mathbf{A}^{*}\right)}} \end{array} \right]^{*} % $$ where $\Sigma^{\dagger}\in \mathbb{R}^{n\times m}$.

Computing $\Sigma$ and $\mathbf{S}$

SVD of (2,1,-2) not ok

Numeric Example

Pseudo-inverse of a matrix that is neither fat nor tall?

When to use $\mathbf{S}$ and when to use $\Sigma$

Dimensions of Singular Value Decomposition Matrices

Manipulating $\Sigma$

The key to using the SVD is to understand the rules for manipulating the sabot matrix. See these examples.

What forms does the Moore-Penrose inverse take under systems with full rank, full column rank, and full row rank?

Visualization of Singular Value decomposition of a Symmetric Matrix

Difference between orthogonal projection and least squares solution

$\endgroup$
1
$\begingroup$

I'm not entirely sure if I'm interpreting what you're saying correctly, so let me write what I think you're asking: If $A=U\Sigma V^T$, and we want to solve $Ax=b,$ you said we'd have $x=V\Sigma^{-1} U^Tb,$ and you want to know why $\Sigma$ is invertible? From this context, it appears that you're assuming that $A$ is invertible, and you're solving a square problem. If we're assuming that $A$ is square, then $U,\Sigma,$ and $V$ are all square, with $U,V$ unitary and $\Sigma$ diagonal.

This comes down to determinant properties. We have $\det A=\det (U\Sigma V^T)=\det U \det \Sigma\det V^T=\det\Sigma,$ and a matrix is invertible if and only if it has non-zero determinant. So, $\Sigma$ being singular would imply that $A$ is singular. Maybe, this isn't as illuminating as to what is going on with the SVD. We're assuming that $A$ is invertible to solve the above. So, all of its eigenvalues are non-zero. $\Sigma$ is the matrix consisting of the singular values, which are the square roots of the eigenvalues of $A^TA.$ So, we have $A^TAv=\sigma^2 v.$ If there were a $\sigma_j$ equal to $0$, $A^TA$ would have a zero eigenvalue, which would then tell us that $0=\det (A^TA)=(\det A)^2$. In fact, if $A$ is symmetric, then $\sigma_j=|\lambda_j|,$ where $\{\lambda_j\}$ denote the eigenvalues of $A$.

EDIT: If $A$ is non-square, then this can be generalized: if $A$ is full rank (say $m\times n$), with $m\geq n$, then we will still have $\Sigma$ invertible, and $V\Sigma^{-1} U^Tb$ will minimize the $2$-norm of $Ax-b.$ $\Sigma$ will be invertible because $A^TA$ is invertible if and only if $A$ has full rank, and since $A^TA=V\Sigma^2 V^T,$ $A$ full rank implies that $\Sigma$ is invertible.

$\endgroup$
5
  • $\begingroup$ Aren't you assuming $A$ is square? $\endgroup$ May 25, 2019 at 13:32
  • $\begingroup$ Based on the presumed context of the problem, I did; it looks to me like they inverted it to solve $Ax=b.$ $\endgroup$
    – cmk
    May 25, 2019 at 13:33
  • $\begingroup$ Maybe, but I would not count on the OP having a clear idea about this. He might not know about the possibility that $A$ is surjective but not square, eg. $\endgroup$ May 25, 2019 at 13:38
  • $\begingroup$ I've edited in a small discussion of the non-square, full rank case. I could add in the rank-deficient case, but I'm pretty sure that the OP is trying to ask a more simplistic question than that. $\endgroup$
    – cmk
    May 25, 2019 at 13:50
  • $\begingroup$ Also, if they aren't aware of the non-square case, then that's probably not what they're asking about. $\endgroup$
    – cmk
    May 25, 2019 at 13:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.