Questions tagged [matrix-decomposition]
Questions about matrix decompositions, such as the LU, Cholesky, SVD (Singular value decomposition) and eigenvalue-eigenvector decomposition.
216
questions
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} ...
- 1,091
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 &...
- 551
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 ...
- 2,980
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 ...
- 1,275
10
votes
3
answers
7k
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 ...
- 8,067
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 ...
- 36k
2
votes
2
answers
1k
views
Problem with Singular Value Decomposition
I have a very trivial SVD Example, but I'm not sure what's going wrong.
The typical way to get an SVD for a matrix $A = UDV^T$ is to compute the eigenvectors of $A^TA$ and $AA^T$. The eigenvectors of ...
- 659
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}$ ...
- 802
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:
$$\...
- 445
4
votes
3
answers
7k
views
Find the eigenvalues of a matrix with ones in the diagonal, and all the other elements equal [duplicate]
Let $A$ be a real $n\times n$ matrix, with ones in the diagonal, and all of the other elements equal to $r$ with $0<r<1$.
How can I prove that the eigenvalues of $A$ are $1+(n-1)r$ and $1-r$, ...
- 61
203
votes
8
answers
116k
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 ...
- 13.8k
8
votes
3
answers
22k
views
How to calculate the cost of Cholesky decomposition?
The cost of Cholesky decomposition is $n^3/3$ flops (A is a $n \times n$ matrix). Could anyone show me some steps to get this number? Thank you very much.
- 81
8
votes
3
answers
1k
views
Prove that the polar decomposition of normal matrices, $A=SU$, is such that $SU=US$
Assume $A$ is a normal matrix. Suppose $A=SU$ is a polar decomposition of $A$. Prove that $SU=US$.
I have no idea to prove this.
$A$ is normal then $AA^*=A^*A$. And then we have
$$
SS^*=U^*S^*SU.
$$
...
- 1,589
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 ...
- 3,452
31
votes
1
answer
58k
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 ...
- 411
15
votes
1
answer
4k
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 ...
- 213
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 ...
user187039
7
votes
1
answer
1k
views
Finding eigenvalues in almost tridiagonal matrix
I need to find the eigenvalues of an $n\times n$ symmetric tridiagonal matrix $A$, except it has $1$s on $A_{1n}$ and $A_{n1}$.
The diagonal entries are all $4$, while superdiagonal and subdiagonal ...
- 73
5
votes
2
answers
290
views
Closed-form solution for the determinant of a Vandermonde-like matrix
I'm trying to find a closed-form solution $\forall$ odd integer $n\ge 3$ for the determinant of a matrix with some structure on it. After some manipulation, I've reduced it to the following matrix:
$\...
- 55
2
votes
1
answer
1k
views
Complexity of Gaussian elimination (LU factorization)
Can someone tell me how to calculate the order of a) $LU$ decomposition as well as b) Gaussian elimination of a square matrix $A$? I am at a loss ...
Given:: $A$ is a $n\times n$ matrix and ultimate ...
- 6,165
2
votes
3
answers
463
views
diagonalisability of matrix few properties
What are the most important things one should remember to check the diagonalisability of a matrix?
Please help, I have exams on next week.
Say some best and easy methods,time efficient.
- 2,010
1
vote
1
answer
997
views
Finding nilpotent and diagonalizable operators for a linear transformation $T$
Let $T$ be the linear operator on $\mathbb{R}^3$ which is represented by the matrix:
$A=\begin{bmatrix}3 & 1 & -1\\ 2 & 2 & -1\\ 2 & 2 &0\end{bmatrix}$
in the standard ordered ...
- 6,494
28
votes
7
answers
14k
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 ...
- 681
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}^{...
- 293
15
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 ...
- 273
12
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 ...
9
votes
2
answers
9k
views
Comparing LU or QR decompositions for solving least squares
Let $X \in R^{m\times n}$ with $m>n$. We aim to solve $y=X\beta$ where $\hat\beta$ is the least square estimator. The least squares solution for
$\hat\beta = (X^TX)^{-1}X^Ty$ can be obtained ...
- 2,495
9
votes
3
answers
12k
views
New proof about normal matrix is diagonalizable.
I try to prove normal matrix is diagonalizable.
I found that $A^*A$ is hermitian matrix. I know that hermitian matrix is diagonalizable.
I can not go more. I want to prove statement use only this ...
- 653
8
votes
2
answers
9k
views
LU factorization of a nonsingular matrix exists if and only if all leading principal submatrices are nonsingular.
I'm struggling to prove this theorem. I can prove that if the $LU$ factorization exists, then the leading principal submatrices are nonsingular.
To do that, I can show that the determinant of every ...
- 81
5
votes
1
answer
586
views
Computation of Cholesky decomposition of Gram matrix from its components
Let's assume I have a tall matrix $\mathbf{X} \in \mathbb{C}^{m\times n}$, where $m \gg n$. I form the Gram matrix $\mathbf{A} = \mathbf{X}^*\mathbf{X}$, where $\mathbf{A} \in \mathbb{C}^{n\times n}$ ...
- 205
5
votes
1
answer
554
views
General Cholesky-like decomposition
For a real positive definite matrix $A$, we can find the Cholesky decomposition $LL^T = A$. If we relax the constraints that L has to be lower triangular, we should be able to find a whole host of ...
- 213
4
votes
2
answers
9k
views
How do I find upper triangular form of a given 3 by 3 matrix??
We are asked to find an invertible matrix $P$ and an upper triangular matrix $U$ such that:
$P^{-1}\begin{pmatrix} 3 & -1 & 1 \\ 2 & 0 & 0 \\ -1 & 1 & 3 \end{pmatrix}P=U$
I'm ...
- 12.7k
3
votes
1
answer
1k
views
Derivative of Symmetric Positive Definite Matrix w.r.t. to its Lower Triangular Cholesky Factor
Setup:
Let $k\in{}\mathbb{N}$ be a natural number, and let $\mathrm{M}_{k,k}(\mathbb{R})$ denote the set of $k\times{}k$ matrices over the field of real numbers.
Let $X\in{}\mathrm{M}_{k,k}(\mathbb{...
3
votes
2
answers
3k
views
Checking if matrix $A$ is positive definite via Cholesky decomposition
How can we show that a matrix $A$ is not a positive definite matrix using the Cholesky decomposition?
If we are not able to complete the algorithm and we cannot factor the matrix with a Cholesky ...
- 14k
3
votes
1
answer
3k
views
Finding an eigenvalue decomposition of a $2m\times 2m$ Hermitian matrix
Let $A$ be an $m\times m$ matrix with entries in $\mathbb{C}$ and with a singular value decomposition $A=U\Sigma V^*$. Find an eigenvalue decomposition of the $2m \times 2m$ Hermitian matrix: $$\begin{...
user265675
3
votes
2
answers
1k
views
Conditions for Schur decomposition and its generalization
Let $M$ be a $n$ by $n$ matrix over a field $F$.
When $F$ is $\mathbb{C}$, $M$ always has a Schur decomposition, i.e. it is always unitarily similar to a triangular matrix, i.e. $M = U T U^H$ where $...
- 47.4k
3
votes
3
answers
3k
views
A rank one matrix can be written in a special form
Any rank one matrix can be written in the form $uv^{t}$, where $u,v$ are column vectors considered as matrices and $t$ denotes transposition.
Why? How?
- 95
2
votes
1
answer
1k
views
Solve for $ A $ from $ A {A}^{T} $
I'm sure that I knew how to do this once many moons ago and that it's really simple.
I have a matrix $ X $ which is defined as:
$$
X = A {A}^{T}
$$
How do I find $ A $ given $ X $?
2
votes
1
answer
323
views
Overlapping positive definite block matrices
Let $A \in \mathbb{R}^{p \times p}$ and $B \in \mathbb{R}^{q \times q}$ be nonsymmetric positive definite matrices in the sense that $v^T A v > 0, \forall v \in \mathbb{R}^p$ and $v^T B v > 0, \...
- 424
2
votes
1
answer
2k
views
How to apply SVD to real data to reduce the number of parameters?
I have a question about applying the Singular Value Decomposition (SVD) to real data. Say I have the equation
$$ y= Ax+v$$
where $A \in \mathbb{R}^{m \times n}$, $y \in \mathbb{R}^m$, $x \in \mathbb{...
- 1,593
1
vote
1
answer
775
views
$SL(n,\mathbb R)$ diffeomorphic to $SO(n) \times \mathbb R^{n(n+1)/2-1}$?
Question : How to show $SL(n,\mathbb R)$ diffeomorphic to $ SO(n) \times \mathbb R^{n(n+1)/2-1}$? Also, how to show $SL(n,\mathbb C)$ diffeomorphic to $ SU(n) \times \mathbb R^{n^2-1}$?
I have ...
- 2,772
33
votes
3
answers
34k
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 ...
- 1,583
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 ...
- 1,069
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. ...
- 367
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 ...
- 243
9
votes
2
answers
4k
views
zeros of $x^*Ax$, a quadratic form
The question hopefully says it all!
We have a Hermitian matrix $A=A^* \in \mathbb{C}^n$ and a quadratic form: $f(x)=x^*Ax,~x\in \mathbb{C}^n$
We want to find the solution of $f(x) = x^*Ax = 0$
When ...
8
votes
1
answer
8k
views
Eigenvalues of product of a matrix with a diagonal matrix
I have got a question and I would appreciate if one could help with it.
Assume $S$ is a diagonal matrix (with diagonal entries $s_1, s_2, \cdots$) and $M$ is a positive symmetric matrix with eigen ...
- 713
8
votes
1
answer
2k
views
Finding Euler decomposition of a symplectic matrix
A symplectic matrix is a $2n\times2n$ matrix $S$ with real entries that satisfies the condition
$$
S^T \Omega S = \Omega
$$
where $\Omega$ is the symplectic form, typically chosen to be $\Omega=\left(...
- 305
8
votes
2
answers
2k
views
Solving the matrix equation $X^tA+A^tX=0$ for $X$ in terms of $A$
Suppose that I know $A$. And all matrices in the equation are square matrices. I want to solve for $X$ given that
$$X^tA + A^tX = 0$$
I'm not really good at matrix calculus. Is it possible to solve ...
- 8,140
7
votes
4
answers
3k
views
Decompose a matrix into diagonal term and low-rank approximation
For a matrix $A$ the Singular Values Decomposition allows getting the closest low-rank approximation $$A_K=\sum_i^K\sigma_i \vec{v}_i \vec{u}_i^T$$ so that $\|A-A_k\|_F$ is minimal.
I'd like to do ...
- 403