Skip to main content

Questions tagged [matrix-decomposition]

Questions about matrix decompositions, such as the LU, Cholesky, SVD (Singular value decomposition) and eigenvalue-eigenvector decomposition.

Filter by
Sorted by
Tagged with
204 votes
8 answers
117k views

Intuitively, what is the difference between Eigendecomposition and Singular Value Decomposition?

I'm trying to intuitively understand the difference between SVD and eigendecomposition. From my understanding, eigendecomposition seeks to describe a linear transformation as a sequence of three basic ...
user541686's user avatar
  • 13.8k
64 votes
4 answers
34k views

How unique are $U$ and $V$ in the singular value decomposition $A=UDV^\dagger$?

According to Wikipedia: A common convention is to list the singular values in descending order. In this case, the diagonal matrix $\Sigma$ is uniquely determined by $M$ (though the matrices $U$ and ...
capybaralet's user avatar
  • 1,275
40 votes
6 answers
33k views

How can you explain the Singular Value Decomposition to non-specialists?

In two days, I am giving a presentation about a search engine I have been making the past summer. My research involved the use of singular value decompositions, i.e., $A = U \Sigma V^T$. I took a high ...
Sidd Singal's user avatar
  • 3,462
34 votes
3 answers
35k views

How is the null space related to singular value decomposition?

It is said that a matrix's null space can be derived from QR or SVD. I tried an example: $$A= \begin{bmatrix} 1&3\\ 1&2\\ 1&-1\\ 2&1\\ \end{bmatrix} $$ I'm convinced that QR (more ...
whitegreen's user avatar
  • 1,593
34 votes
1 answer
28k views

Computing the Smith Normal Form

Let $A_R$ be the finitely generated abelian group, determined by the relation-matrix $$R := \begin{bmatrix} -6 & 111 & -36 & 6\\ 5 & -672 & 210 & 74\\ 0 & -255 &...
Euden's user avatar
  • 551
34 votes
6 answers
2k views

Proof that $\text{det}(AB) = \text{det}(A)\text{det}(B)$ without explicit expression for $\text{det}$

Overview I am seeking an approach to linear algebra along the lines of Down with the determinant! by Sheldon Axler. I am following his textbook Linear Algebra Done Right. In these references the ...
Jagerber48's user avatar
  • 1,441
31 votes
1 answer
59k views

When does a Square Matrix have an LU Decomposition?

When can we split a square matrix (rows = columns) into it’s LU decomposition? The LUP (LU Decomposition with pivoting) always exists; however, a true LU decomposition does not always exist. How do ...
Highrule's user avatar
  • 411
30 votes
2 answers
24k views

LU Decomposition vs. Cholesky Decomposition

What is the difference between LU Decomposition and Cholesky Decomposition about using these methods to solving linear equation systems? Could you explain the difference with a simple example? Also ...
mertyildiran's user avatar
28 votes
7 answers
15k views

Understanding the singular value decomposition (SVD)

Please, would someone be so kind and explain what exactly happens when Singular Value Decomposition is applied on a matrix? What are singular values, left singular, and right singular vectors? I know ...
Celdor's user avatar
  • 681
27 votes
5 answers
4k views

Let $A=(a_{ij})$ be an $n\times n$ matrix. Suppose that $A^2$ is diagonal. Must $A$ be diagonal?

Let $A=(a_{ij})$ be an $n\times n$ matrix. Suppose that $A^2$ is diagonal? Must $A$ be diagonal. In other words, is it true that $$A^{2}\;\text{is diagonal}\;\Longrightarrow a_{ij}=0,\;i\neq j\;\;?...
Medo's user avatar
  • 3,150
27 votes
4 answers
10k views

Is it true that any matrix can be decomposed into product of rotation, reflection, shear, scaling and projection matrices?

It seems to me that any linear transformation in ${\Bbb R}^{n \times m}$ is just a series of applications of rotation — actually i think any rotation can be achieved by applying two reflections, but ...
Sunny88's user avatar
  • 1,069
26 votes
8 answers
26k views

Relation between Cholesky and SVD

When we have a symmetric matrix $A = LL^*$, we can obtain L using Cholesky decomposition of $A$ ($L^*$ is $L$ transposed). Can anyone tell me how we can get this same $L$ using SVD or Eigen ...
Gatsu's user avatar
  • 325
23 votes
2 answers
6k views

The benefit of LU decomposition over explicitly computing the inverse

I'm going to teach a linear algebra course in the fall, and I want to motivate the topic of matrix factorizations such as the LU decomposition. A natural question one can ask is, why care about this ...
user avatar
22 votes
1 answer
3k views

How to understand the spectral decomposition geometrically?

Let $A$ be a $k\times k$ positive definite symmetric matrix. By spectral decomposition, we have $$A = \lambda_1e_1e_1'+ ... + \lambda_ke_ke_k'$$ and $$A^{-1} = \sum_{i=1}^k\frac{1}{\lambda_i}...
Jill Clover's user avatar
  • 4,797
20 votes
1 answer
38k views

LU decomposition steps

I've been looking at some LU Decomposition problems and I understand that making a matrix A reduced to the form A=LU , where L is a lower triangular matrix and U is a upper triangular matrix, however ...
Sujaan Kunalan's user avatar
19 votes
5 answers
11k views

Find the inverse of a submatrix of a given matrix

I have a $A$ matrix $4 \times 4$. By delete the first row and first column of $A$, we have a matrix $B$ with sizes $3 \times 3$. Assume that I have the result of invertible A that denote $A^{-1}$ ...
John's user avatar
  • 802
19 votes
1 answer
26k views

Decomposition of a positive semidefinite matrix

Let $Y \in \mathbb{R}^{n \times n}$ be a symmetric, positive semidefinite matrix such that $Y_{kk} = 1$ for all $k$. This matrix is supposed to be factorized as $Y = V^T V$, where $V \in \mathbb{R}^{...
nlassaux's user avatar
  • 293
19 votes
1 answer
5k views

Cholesky of matrix plus identity

I have a positive definite matrix $A$ ($n \times n$ dimension) for which I have the Cholesky decomposition $A=LL^{'}$. I want to use this to compute a) The Cholesky decomposition of $A+c^2\times I $ ...
Abhirup Datta's user avatar
16 votes
2 answers
3k views

Inverse of the sum of a invertible matrix with known Cholesky-decomposion and diagonal matrix

I want to ask a question about invertible matrix. Suppose there is a $n\times n$ symmetric and invertible matrix $M$, and we know its Cholesky decomposion as $M=LL'$. Then do we have an efficient way ...
Eridk Poliruyt's user avatar
16 votes
3 answers
5k views

LU decomposition; do permutation matrices commute?

I have an assignment for my Numerical Methods class to write a function that finds the PA=LU decomposition for a given matrix A and returns P, L, and U. Nevermind the coding problems for a moment; ...
BenL's user avatar
  • 991
15 votes
3 answers
22k views

Why does the Cholesky decomposition requires a positive definite matrix?

Why does the Cholesky factorization requires the matrix A to be positive definite? What happens when we factorize non-positive definite matrix? Let's assume that ...
Memleak's user avatar
  • 335
15 votes
2 answers
7k views

Every $n\times n$ matrix is the sum of a diagonalizable matrix and a nilpotent matrix.

I would like to prove that every $n\times n$ matrix is the sum of a diagonalizable matrix and a nilpotent matrix. How is this possible? I'm not sure where to begin really- I know that a nilpotent ...
user avatar
15 votes
3 answers
32k views

Time complexity of LU decomposition

I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix. Eliminating the first column will require $n$ additions and $n$ multiplications for $n-1$ rows. Therefore, the ...
amaatouq's user avatar
  • 505
15 votes
1 answer
5k views

Singular values of $AB$ and $BA$ where $A$ and $B$ are rectangular matrices

This question is a generalisation of Eigenvalues of $AB$ and $BA$ where $A$ and $B$ are rectangular matrices which itself is a generalisation of Eigenvalues of $AB$ and $BA$ where $A$ and $B$ are ...
LBogaardt's user avatar
  • 213
15 votes
2 answers
5k views

Most efficient method for computing Singular Value Decomposition of a triangular matrix?

There are several methods available for computing SVD of a general matrix. I am interested in knowing about the best approach which could be used for computing SVD of an upper triangular matrix. ...
sv_jan5's user avatar
  • 367
14 votes
2 answers
13k views

RQ decomposition

Can someone explain me how we can compute RQ decomposition for a given matrix (say, $3 \times 4$). I know how to compute QR decomposition. I know the function in MATLAB which computes this RQ ...
krish's user avatar
  • 175
14 votes
3 answers
9k views

To what extent is the Singular Value Decomposition unique? [duplicate]

In Adam Koranyi's article "Around the finite dimensioal spectral theorem", in Theorem 1 he says that there exist unique orthogonal decompositions. What is meant here by unique? We know that the ...
Mambo's user avatar
  • 585
14 votes
1 answer
11k views

Khatri-Rao product example

I am trying to understand the following definition of the Khatri-Rao product taken from Kolda, Tamara G., and Brett W. Bader. "Tensor decompositions and applications."(2009): "The Khatri-Rao product ...
lspinheiro's user avatar
14 votes
1 answer
4k views

Why is the non-negative matrix factorization problem non-convex?

Supposing $\mathbf{X}\in\mathbb{R}_+^{m\times n}$, $\mathbf{Y}\in\mathbb{R}_+^{m\times r}$, $\mathbf{W}\in\mathbb{R}_+^{r\times n}$, the non-negative matrix factorization problem is defined as: $$\...
no_name's user avatar
  • 445
14 votes
3 answers
21k views

Cholesky decomposition of the inverse of a matrix

I have the Cholesky decomposition of a matrix $M$. However, I need the Cholesky decomposition of the inverse of the matrix, $M^{-1}$. Is there a fast way to do this, without first computing $M^{-1}$? ...
user1971988's user avatar
14 votes
1 answer
6k views

Connection between SVD and Discrete Fourier Transform for Denoising

Denoising signals (in particular, 2D arrays, such as images) can be done by removing the high frequency components of the discrete Fourier transform (which is related to convolution with a Gaussian ...
user3658307's user avatar
  • 10.4k
14 votes
3 answers
1k views

A criteria for Jordan decomposition of a matrix over a general ring

When I look at different proofs of the Jordan-Chevalley decomposition of a matrix, the minimal hypothesis I usually found is about the perfection of the field over which such decomposition occurs (e.g....
brunoh's user avatar
  • 2,456
13 votes
1 answer
19k views

How to prove the existence and uniqueness of Cholesky decomposition?

Given a real Hermitian positive-definite matrix $A$ is a decomposition of the form $A=L L^T$ where L is a lower triangular matrix with positive diagonal entries. I read some proofs about the existence ...
You_Don't_Know_Who's user avatar
13 votes
1 answer
6k views

Why is the largest element of symmetric, positive semidefinite matrix on the diagonal?

I know the very well know equivalence of the properties of a positive, semidefinite matrix: $A$ is positive semidefinite, $A = U^T U$ for some matrix $U$, $\mathbf{x}^T A \mathbf{x}\geq 0$ for every $...
Filip M's user avatar
  • 329
13 votes
2 answers
34k views

When eigenvectors for a matrix form a basis

It is well known that if n by n matrix A has n distinct eigenvalues, the eigenvectors form a basis. Also, if A is symmetric, the same result holds. Consider $ A =\left[ {\begin{array}{ccc} 1 &...
user155214's user avatar
13 votes
1 answer
3k views

If $\mathrm{Tr}(A)=0$ then $T=R^{-1}AR$ has all entries on its main diagonal equal to $0$

Prove that if $A$ is a square matrix and $\mathrm{Tr}(A)=0$, then there exists an invertible matrix $R$ such that the matrix $T=R^{-1}AR$ has all entries on its main diagonal equal to $0$. It seems ...
Tien Kha Pham's user avatar
13 votes
4 answers
11k views

Find diagonal of inverse matrix

I have computed the Cholesky of a positive semidefinite matrix $\Theta$. However, I wish to know the diagonal elements of the inverse of $\Theta^{-1}_{ii}$. Is it possible to do this using the ...
sachinruk's user avatar
  • 931
12 votes
1 answer
11k views

A normal matrix with real eigenvalues is Hermitian

$A$ is a normal matrix (i.e. $AA^*=A^*A$, where * denotes the hermitian conjugate). If all its eigenvalues are real, prove that it is Hermitian (i.e. $A^*=A$). I have tried many things but could not ...
Myshkin's user avatar
  • 36.1k
12 votes
1 answer
19k views

Solving a linear system with Cholesky factorization

So, I've reached the following problem: Given $A \in R^{nxn} $ positive-definite and symmetrical, $B\in R^{nxn}$ and the vector $c\in R^n$ write an algorithm to solve to following situation: $Ax=Bc$ ...
Speedy .RoGamer's user avatar
12 votes
3 answers
13k views

Calculating SVD by hand: resolving sign ambiguities in the range vectors.

When calculating the SVD of the matrix $$A = \begin{bmatrix}3&1&1\\-1&3&1\end{bmatrix}$$ I followed these steps $$A A^{T} = \begin{bmatrix}3&1&1\\-1&3&1\end{bmatrix} ...
Crimson's user avatar
  • 1,091
12 votes
1 answer
7k views

Decompose a 2D arbitrary transform into only scaling and rotation

Related to: Newly Developed With Details - Describing orthographic projection using simple 2D transformations Given an arbitrary 2D linear transform (which may include shear, i.e. the vectors or the ...
Pedro Gimeno's user avatar
12 votes
2 answers
5k views

How to find the Takagi decomposition of a symmetric (unitary) matrix?

The Takagi decomposition is a special case of the singular value decomposition for symmetric matrices. More exactly: Let $U$ be a symmetric matrix, then Takagi tells us there is a unitary $V$ ...
Ruben Verresen's user avatar
11 votes
5 answers
18k views

Is the $L$ in $LU$ factorization unique?

I was doing an $LU$ factorization problem \begin{bmatrix} 2 & 3 & 2 \\ 4 & 13 & 9 \\ -6 & 5 &4 \end{bmatrix} and I was going to multiply the second row by ...
thecat's user avatar
  • 1,848
11 votes
4 answers
1k views

Prove $\rm AB = BA = 0$ if the set of nonzero eigenvalues of $\rm A + B$ is union of set of nonzero eigenvalues of $\rm A$ and $\rm B$.

$A$ and $B$ are $n×n$ symmetric matrices, their non-zero eigenvalues are $(\lambda_{1},\ldots,\lambda_{r} )$,$( \mu_{1},\ldots,\mu_{s} )$. If the nonzero eigenvalues of $A + B$ are $(\lambda_{1},\...
z3wood's user avatar
  • 1,105
11 votes
2 answers
245 views

Is there an iterative procedure that pushes the singular values of a matrix toward unity?

Consider a square matrix $A = U \Sigma V^T$. I want to find $B = UV^T$ — however, it seems wasteful to compute the whole SVD just to re-multiply the two orthogonal matrices. Does there exist some ...
Nick's user avatar
  • 1,017
11 votes
0 answers
196 views

Expressing diagonal matrix using elementary matrices as generators in $\operatorname{SL}(\mathcal O_K \oplus \mathfrak a)$

Let $K$ be a real quadratic number field, $\mathcal O_K$ its ring of integers and an $\mathfrak a \subset K$ a fractional ideal. I've read in van der Geer that the group $$\operatorname{SL}(\mathcal ...
principal-ideal-domain's user avatar
10 votes
3 answers
8k views

Polar decomposition of real matrices

Can we decompose real matrices in a way that is analogous to polar decomposition in the complex case? What I mean is: given an invertible real matrix $M$, can we always write: $$ M = OP, $$ maybe ...
geodude's user avatar
  • 8,097
10 votes
2 answers
10k views

What is the Cholesky Decomposition used for?

It seems like a very niche case, where a matrix must be Hermitian positive semi-definite. In the case of reals, it simply must be symmetric. How often does one have a positive semi-definite matrix in ...
Axoren's user avatar
  • 2,313
10 votes
2 answers
13k views

Proof of uniqueness of LU factorization

The first question: what is the proof that LU factorization of matrix is unique? Or am I mistaken? The second question is, how can theentries of L below the main diagonal be obtained from the matrix $...
Tashima Sasaki's user avatar
10 votes
1 answer
811 views

Determinant of matrix with binomial coefficients entries

I try that find the way for calculate the determinant of the following matrix of size $n\times n$. The determinant is $\displaystyle\binom{k+n}{k}x^{n}$. I wait that you can help me. THE OMITTED ...
Luis Prado's user avatar

1
2 3 4 5
54