Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [matrix-decomposition]

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

23
votes
5answers
3k 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\;\;?...
22
votes
1answer
13k 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 &...
16
votes
2answers
1k 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 ...
14
votes
3answers
9k views

null space from SVD

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 ...
13
votes
2answers
2k 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. ...
13
votes
1answer
2k 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 $ ...
12
votes
3answers
322 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....
11
votes
5answers
778 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},\...
11
votes
1answer
3k 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 ...
11
votes
2answers
181 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 ...
11
votes
1answer
396 views

Matrix factorization

I'd like to factorize matrices as follows: $$ \left(\begin{array}{cc}X_1&X_2\\X_3&X_4\end{array}\right) = \left(\begin{array}{cc}D_1&D_2\\D_3&D_4\end{array}\right)\left(\begin{array}{...
11
votes
1answer
5k 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 ...
10
votes
1answer
816 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 ...
9
votes
2answers
5k views

Matrix exponential of a skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. Question 1) How do I compute $e^{...
9
votes
1answer
3k 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 ...
9
votes
1answer
3k 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 ...
9
votes
1answer
231 views

A very difficult problem about the existence of following $SU(2)$ matrices?

Let $G_i$ be a sequence of $SU(2)$ matrices, where $i=1,2,...,n$; and $P$ represents a permutation of $\left \{ 1,2,...,n \right \}$. The question is: Does there exist a sequence of $SU(2)$ matrices ...
8
votes
2answers
918 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 ...
8
votes
3answers
5k 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} ...
8
votes
3answers
9k 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 ...
8
votes
3answers
2k 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; ...
8
votes
2answers
2k views

Inverse of the sum of a symmetric and diagonal matrices

I have two matrices $A$ and $B$ with quite a few notable properties. They are both square. They are both symmetric. They are the same size. $A$ has $1$'s along the diagonal and real numbers in $(0 ...
8
votes
1answer
214 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 ...
8
votes
1answer
161 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 ...
7
votes
1answer
3k 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 $...
7
votes
4answers
4k views

Find diagonal of inverse matrix

I have computed the Cholesky of a positive semidifinite 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 cholesky ...
7
votes
2answers
151 views

A special case: determinant of a $n\times n$ matrix

I would like to solve for the determinant of a $n\times n$ matrix $V$ defined as: $$ V_{i,j}= \begin{cases} v_{i}+v_{j} & \text{if} & i \neq j \\[2mm] (2-\beta_{i}) v_{i} & \text{if} &...
7
votes
2answers
323 views

Properties of matrices $M=UDU^*$ with $UU^*=Id$

I recently came across some matrices of the form $M=UDU^*$ (the superscript $*$ denotes the conjugate transpose), where $U \in \mathbb{C}^{r\times n}$ with $r<n$, $D \in \mathbb{C}^{n \times n}$ a ...
7
votes
0answers
164 views

Simplifying Trace of a Matrix Expression ${\rm Tr} \left( (I- D^{-1} BA^2) B (I- D^{-1} BA^2)^T \right)$

Let $B$ be a symmetric invertible matrix and let $A$ be a diagonal matrix with non-zero entries on the main diagonal. I am trying to simplify the following expression \begin{align} {\rm Tr} \left( ...
6
votes
1answer
4k 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 ...
6
votes
3answers
4k 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}$ ...
6
votes
1answer
5k 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 ...
6
votes
1answer
6k 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}^{...
6
votes
2answers
199 views

Finding minimum from matrix

Consider following $3\times 3$ matrix. $\begin{pmatrix}3&6&9\\ 2& 4 &8\\ 1 &5& 7 \end{pmatrix}$ I need to find combination of three numbers where each number ...
6
votes
1answer
3k views

A real life application for QR decomposition

I need to use the QR decomposition of a matrix for a real life application, (use it on a particular matrix form) and I have no idea what to do. Can you suggest me a real life application for this? ...
6
votes
3answers
104 views

Matrices that Differ only in Diagonal of Decomposition

Suppose that $\mathbf A_1$ and $\mathbf A_2$ are $n \times n$ matrices. Are there necessary and sufficient conditions such that there exists $n \times n$ matrices $\mathbf U$ and $\mathbf V$ and $n \...
6
votes
1answer
1k views

$QR$ decomposition of rectangular block matrix

So I am running an iterative algorithm. I have matrix $W$ of dimensions $n\times p$ which is fixed for every iteration and matrix $\sqrt{3\rho} \boldsymbol{I}$ of dimension $p\times p$ where the $\rho$...
6
votes
1answer
137 views

Generators of $GL_2(\mathbb{Q}_p)$

A well known fact is that the group $GL_2(\mathbb{Q}_p)$ is generated by the following matrices: $1) \text{ } w= \left( {\begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} } \right)...
6
votes
2answers
105 views

Let $P \in M_n(\mathbb C)$ be idempotent. Prove that all nonzero singular values of $P$ satisfy $\sigma_i \ge 1$

I'm having some difficulty proving the following: Let $P \in M_n(\mathbb C)$ be idempotent. Prove that all nonzero singular values of $P$ satisfy $\sigma_i \ge 1$. By definition I know that $P$ ...
6
votes
1answer
464 views

Expressing a quadratic form, $\mathbf{x}^TA\mathbf{x}$ in terms of $\lVert\mathbf{x}\rVert^2$, $A$

EDIT: This question is actually an attempt to solve this. Please take a look. Let $A$ be a symmetric postive-definite $n\times n$ matrix, i.e. $A\in\mathbb{S}_{++}^{n}$ Also, let $\mathbf{x}\in\...
6
votes
0answers
560 views

Can I go from the LU factorization of a symmetric matrix to its Cholesky factorization, without starting over?

I mistakenly computed the LU factorization and then realized that the question is asking for a Cholesky factorization, i.e., finding a lower triangular matrix L such that the symmetric matrix A has ...
5
votes
1answer
4k 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 ...
5
votes
1answer
39 views

Does the following hold for any matrix $A$ with non-negative eigenvalues?

If $A\in\Re^{q\times{q}}$ is a square matrix with non-negative eigenvalues. Is it possible to show that $x^TAx\geq{0}$ for any non-zero vector $x$? I know this is obvious for positive semi-definte ...
5
votes
1answer
529 views

Principal component analysis (PCA) results in sinusoids, what is the underlying cause?

Background I'm analysing a data set of $M$ flow measurements (volume per time). The flows go from zero mL/s gradually to higher values and back to zero again, thus: their shapes ideally look like a ...
5
votes
2answers
15k views

Easy way to calculate inverse of an LU decomposition.

I have a matrix A and a lower triangular matrix L (with 1's along the diagonal) and an upper triangular matrix U. These are constructed such that $A=LU$. I know that $A^{-1} = L^{-1}U^{-1}$ and I know ...
5
votes
1answer
93 views

Invertibility of $U+I$ where $U$ comes from a SVD $M=USV'$

Assume that $U$ is a real $2 \times 2$ matrix arising from a singluar value decomposition $$ M = USV' $$ As a part of a bigger calculation, it suggested in this paper (see text right beneath equation ...
5
votes
1answer
390 views

QR factorization of a special structured matrix

A friend asked me the following interesting question: Let $$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$ where $R \in \mathbb{R}^{n \times n}$ is an upper triangular and ${\rm I}$ ...
5
votes
1answer
132 views

Can $A^{T}(AA^{T})^{-1}A$ be simplified?

Let $A$ is an $m\times n$ ($m<n$) real matrix with full positive entries and $\text{Rank}(A)=m$. Thus $(AA^{T})^{-1}$ is an $m\times m$ symmetric $M$-matrix since $AA^{T}$ is nonnegtive and ...
5
votes
1answer
352 views

Finding the Jordan Canonical form of a $6 \times 6$ matrix

Find the Jordan Canonical Form of the following matrix $$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 &...
5
votes
2answers
4k 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}$? ...