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.

986 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
0 answers
342 views

Matrix powers of product of diagonalizable and orthogonal matrix

Suppose I have the following matrix constructed from some orthogonal matrix $O$ and a $\pm 1$ diagonal matrix $D=diag(\pm1,\dots,\pm1)$ $$ A = O D O^{-1} D. $$ Is there a simple way to evaluate $A^n$ ...
User71942's user avatar
  • 119
9 votes
0 answers
2k 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 ...
User001's user avatar
8 votes
1 answer
213 views

Triangularization of matrix over PID

Let $R$ be a PID and let $A \in Mat_n(R)$ with all of its eigenvalues in R. Is it true that I can always find $P \in GL_n(R)$ such that $P^{-1}AP$ is uppertriangular? If so can I have a reference ...
Larry's user avatar
  • 81
8 votes
0 answers
11k views

Decompose 3D rotation matrix into rotation around x, y and z-axis

I have a rotation matrix R, that produces an arbitrary rotation in a 3D space. I would like to decompose it into 3 rotation matrices Rx, Ry and Rz so I can use and apply only xy in plane rotation (...
Ricardo Domingos Ferreira's user avatar
7 votes
0 answers
358 views

Fast arbitrary decomposition of a positive-definite matrix

Given a positive-definite $n\times n$ matrix $\mathbf{A}$, my goal is to present it as a product of the form $\mathbf{H^TH}$, where $\mathbf{H}$ is an arbitrary $n\times n$ matrix. Cholesky ...
Sergey Guminov's user avatar
7 votes
1 answer
231 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( ...
Boby's user avatar
  • 6,015
7 votes
0 answers
655 views

Cholesky decomposition of $A+kI$ given Cholesky decomposition of A

Suppose I have the Cholesky decomposition for a symmetric matrix $A$: $$ A = L L^T $$ I wish to compute the Cholesky decomposition for $A+kI$ where $I$ is the identity and $k$ is a scalar. Is there ...
Alex Flint's user avatar
5 votes
0 answers
216 views

Dimension free gram matrix inner product

Let $\{x_i\}_{i = 1}^n$ be $n$ vectors of $d$ dimesnions. We stack each $x_i$ as a row vector to form a matrix $X$ of dimension $\mathbb{R}^{n\times d}$ Let $\{y_i\}_{i = 1}^n$ be scalars (say all are ...
rostader's user avatar
  • 479
5 votes
0 answers
46 views

Difference of positive semi-definite matrices

If we have $S$ positive semi-definite matrices $A_1,\dots, A_S$ then what is the largest matrix positive semi definite matrix C such that $A_s -C$ is also psd for all $s=1,\dotsc,S$? By largest I mean ...
noirritchandra's user avatar
5 votes
0 answers
2k views

Convergence of the complex QR algorithm to Schur decomposition

I study the complex Schur decomposition of a complex matrix $A \in \mathbb{C}^{n \times n}$, that is: $$ A = U T U^H $$ where $T$ is upper-triangular (the eigenvalues of $A$ appear on its diagonal, ...
Triceratops's user avatar
5 votes
3 answers
5k views

Huge matrix multiplication

I have a sparse A matrix stored in column major order (it is intrisically column major) of ~80GB and another sparse matrix B relatively small (1GB) which can be loaded in row or column major with no ...
Alessandro Pilleri's user avatar
5 votes
0 answers
560 views

What happens to woodbury matrix identity when A is not invertible?

The Woodbury matrix identity is \begin{equation} (A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}. \end{equation} This formula suppose that $A$, $(A+UCV)$ and $(C^{-1}+VA^{-1}U)$ are ...
G. Trav's user avatar
  • 389
5 votes
0 answers
8k views

Checking positive semidefiniteness in MATLAB

Let $\mathbf{A}$ be a $n\times n$ matrix. I want to check in MATLAB if it is PSD or not. Which tests, in MATLAB, should I do for this purpose? I know that if $\mathbf{A}$ is PSD then following holds ...
NAASI's user avatar
  • 997
5 votes
0 answers
627 views

Is there a decomposition $U U^T$?

We know that there exist the Choleski decomposition $ M = L L^T $ where $M$ is a positive definite matrix and $L$ a lower triangular one. Does it exist a similar decomposition in $ M = U U^T$ ...
johnhenry's user avatar
  • 249
4 votes
0 answers
47 views

Is it possible to factor a huge matrix (SVD or NMF) without never computing it?

I have a linear function $u$ from approximately $\mathbb{R}^{10^6} \to \mathbb{R}^{3\times10^5}$. It has a certain computing cost so I would like to approximate it using a factored matrix ...
aJuv's user avatar
  • 101
4 votes
0 answers
430 views

SVD of “almost” block diagonal matrix

It is possible to show that SVD of block diagonal matrix is equivalent to independent SVDs of each block. I am wondering if there is something interesting to say on the case where the matrix is ...
user1767774's user avatar
4 votes
1 answer
564 views

How to prove that the singular value of product of two orthonormal matrix is related to the principal angles between their columns space?

Assume that $A$, $B$ $\in R^{p\times d}$ both have orthonormal columns, then the vector of $d$ principal angles between their column spaces is give by $(\cos^{-1}\sigma_1,\cos^{-1}\sigma_2, \dots, \...
Nicolas H's user avatar
  • 211
4 votes
0 answers
689 views

Why positive diagonal entries in Cholesky decomposition?

I don't understand why L must have strictly positive diagonal entries in Cholesky decomposition?: $A = L*L^{T}$
Shrike Danny's user avatar
4 votes
0 answers
428 views

A closed-form formula for the derivative of the matrix absolute value

$\newcommand{\psym}{\text{Psym}_n}$ $\newcommand{\sym}{\text{sym}}$ $\newcommand{\Sym}{\operatorname{Sym}}$ $\newcommand{\Skew}{\operatorname{Skew}}$ $\renewcommand{\skew}{\operatorname{skew}}$ $\...
Asaf Shachar's user avatar
  • 25.3k
4 votes
0 answers
1k views

Implementation of Youla Decomposition for a square skew-symmetric matrix

I am looking for a publicly-available software package (preferably in Python, but I'll take what I can get) capable of performing a decomposition of a real $n\times n$ skew-symmetric (sometimes called ...
Surgical Commander's user avatar
4 votes
0 answers
1k views

Multivariate polynomials as matrix products?

Sorry if this is a silly question. But if I have a polynomial in two variables, with the maximum degree of each individual variable no greater than N, $$p(x, y)=c_{00}+c_{10}x+c_{01}y+c_{11}xy+c_{20}...
dizzy77's user avatar
  • 166
4 votes
0 answers
50 views

Sufficient/necessary condition for submatrix determinant (minor) that decreases with size?

Definition. Given a square matrix ${\bf{A}}=[a_{ij}] \in {\mathbb{C}^{n \times n}}$, the submatrix ${{\bf{A}}_{{i_1},{i_2},...{i_k}}}$ is formed by retaining the $({i_1},{i_2},...{i_k})$-th rows and ...
paradis's user avatar
  • 121
4 votes
0 answers
701 views

Show that partial pivoting leads to an $LU$ decomposition of $PA$.

Exercise: show that for every non-singular matrix $A$, partial pivoting leads to an $LU$ decomposition of $PA$ so: $PA = LU$. I have the following theorems I can use: Theorem 1: Assume that the ...
titusAdam's user avatar
  • 2,877
4 votes
0 answers
349 views

Is a principal submatrix of a diagonalizable matrix diagonalizable?

Let $A$ be diagonalizable, i.e., $A=X \Lambda X^{-1}$ for some diagonal matrix $\Lambda$. Consider $B$ which is a principal submatrix of $A$. Does there exist an invertible matrix $Y$ and a diagonal ...
Ozzy's user avatar
  • 387
4 votes
0 answers
659 views

PCA derivation by minimizing reconstrution squared error plus orthonormality constraints

I'm trying to better understand the link between PCA and Matrix Factorization of the form $X \approx WH$. I've read somewhere that the PCA solution can be also derived from the following cost ...
alberto's user avatar
  • 213
4 votes
0 answers
424 views

Eigenvalues of a tridiagonal matrix with corners (periodic tridiagonal, cyclic tridiagonal)

I have conjectured that the eigenvalues of the following $N\times N$ matrix are all distinct: $$\mathbf{A}=\left[\begin{array}{ccccccc} \sin\left(\frac{2\pi 0}{N} \right)&-\frac{1}{2}&&&...
Juliano Lima's user avatar
4 votes
0 answers
137 views

To what extent are the Jordan-Chevalley and Levi Decompositions compatible.

I know that the Jordan-Chevalley decomposition for real Lie algebras only applies to semisimple Lie algebras, but in general the addititive J-C decomposition says that for ANY operator, we can ...
Ironbeard's user avatar
  • 215
4 votes
1 answer
2k views

How to compute QR decomposition of a product of matrices

Suppose I have $A=A_nA_{n-1}\cdots A_2A_1$ How can I compute the $QR$ factorization of $A$ without explicitly multiplying $A_1, A_2, \ldots, A_n$ together? The suggestion I got is that, suppose $n=3$...
AbcXYZ's user avatar
  • 440
4 votes
1 answer
516 views

Sum of Nonnegative Matrix and Diagonal Matrix

Setup: Let $D = D^T > 0$ be a positive definite and diagonal $n\times n$ matrix, and let $A = A^T \in \mathbb{R}^{n\times n}$ be nonnegative with zero diagonals. That is, $a_{ij} \geq 0$ for $i\neq ...
John's user avatar
  • 417
3 votes
0 answers
44 views

When do symmetrical matrices commute?

For context I was taking an optimization course and at one point we used the restriction by line to prove the concavity of $\log det(X)$. Let $g(t) = \log det(X + tV)$ with $V \in S_{n}$ and $t \in \...
Peregrint's user avatar
3 votes
0 answers
95 views

Weighted Nearest Kronecker Product

For a given $m n$-length vector $a$, the problem of finding an $m$-length vector $x$ and an $n$-length vector $y$ that minimize $$ \lVert a - x \otimes y \rVert^2 $$ is known as the Nearest Kronecker ...
Black Shield Bearer's user avatar
3 votes
0 answers
57 views

How was the singular value decomposition originally derived? How might one discover this decomposition from first principles?

How was the singular value decomposition (SVD) method originally derived? How might one discover decomposition this from first principles? Related Q&As that lend intuition to SVD but not derive ...
fool's user avatar
  • 217
3 votes
0 answers
34 views

Eigenvalue decompositin equal to singular value decomposition

Question: when is the eigenvalue decomposition of a matrix equal to its singular value decomposition? Answer: when A is hermitic and has positive eigenvalues. I don't really understand. If we have A=A*...
anoniem's user avatar
  • 291
3 votes
0 answers
506 views

Reducing a Hermitian tridiagonal matrix to real symmetric tridiagonal form

Edit: I have now found the answer myself, and will write it up nicely on this coming weekend. A complex Hermitian matrix is unitarily similar to a real symmetric tridiagonal matrix, which one computes ...
James's user avatar
  • 142
3 votes
0 answers
75 views

Analogues of Iwasawa Decomposition for $\operatorname{SL}_2(\mathbb{R})/\operatorname{SO}(1,1)(\mathbb{R})$

Consider the group $\operatorname{SL}_2(\mathbb{R})$. The set of positive-definite symmetric $2 \times 2$ matrices of determinant $1$ constitutes a symmetric space $S^+$ for $\operatorname{SL}_2(\...
Ashvin Swaminathan's user avatar
3 votes
0 answers
86 views

Decomposition of a 4D rotation into a particular sequence of simple rotations.

It is known that any rotation in $SO(n)$ can be decomposed into a particular sequence of $n(n-1)/2$ simple rotations (that is, rotations which rotate a 2D plane in $\mathbb{E}^n$). The procedure to ...
3Brown1Blue's user avatar
3 votes
0 answers
40 views

Relation between the eigendecomposition a PD matrix and its entry-wise positive counterpart

Suppose that we have a positive definite matrix $X$ and its entry-wise positive version $Y=|X|$ where $\forall i, j \;\; y_{ij}=|x_{ij}|$. Is there any relationship between their eigen-decompositions, ...
Qtip's user avatar
  • 75
3 votes
0 answers
237 views

Is the Singular Value Decomposition a measurable function?

Consider the SVD of rectangular matrices as operators $$ svd : \mathbb C^{n\times m} \to \mathbb U_n \times \mathbb D_{n,m}\times \mathbb U_m $$ where $\mathbb U$ is the space of $n\times n$ unitary ...
Exodd's user avatar
  • 11k
3 votes
0 answers
88 views

Matrix with different dimensions and same eigenvalues (multiplicity)

Suppose we have two positive definite symmetric matrices $A\in\mathbb{R}^{m\times m}$ and $B\in\mathbb{R}^{(m+1)\times (m+1)}$. In particular, $B\equiv \left( \begin{matrix} a_{11} & ... & a_{...
L.D.Damono's user avatar
3 votes
0 answers
855 views

QR factorization and Schur decomposition

The $QR$ factorization provides us with a way to write every real matrix $A$ in the form of $QR$, with $Q$ being an orthogonal matrix and $R$ being an upper triangular matrix. I believe that there ...
Sam Wong's user avatar
  • 2,277
3 votes
0 answers
146 views

A specific coset decomposition of $\mathrm{GL}_n(\mathbb{C})$

I am reading an old paper [1] where they introduce a specific decomposition of a complex, invertible matrix. There is no proof, so I am trying to come up with one. The claim goes as follows: Let $\...
Mads G's user avatar
  • 31
3 votes
0 answers
105 views

Prove that all eigenvalues $((C^T(Q_f+Q_p)C)^{-1} (C^T(Q_g+Q_p)C)) \geq ((C^TQ_fC)^{-1} (C^TQ_gC))$ ??

Consider symmetric positive definite matrices $X_{f} = (C^TQ_fC)^{-1}$, $~~ X_{g} = (C^TQ_gC)^{-1}$, $~~X_{fp} = (C^T(Q_f+Q_p)C)^{-1}$, $~~ X_{gp} = (C^T(Q_g+Q_p)C)^{-1}$, where $C \in \mathbb{R}^{n \...
rookie_OP's user avatar
3 votes
0 answers
154 views

Under what conditions of $A,B$ we have $\det (A + \lambda B)$ is uniformly $0$ for all $\lambda$?

Assume $A,B$ are real-value symmetric matrix (maybe redundant condition) and $\lambda \in \mathbb{R}$. This question comes from here, but the answerer doesn't give the condition.
wz0919's user avatar
  • 157
3 votes
0 answers
395 views

Maximizing tr(AB) under a rotation matrix constraint for B? Related to von Neumann's trace inequality

Let $\mathbf{A}$ and $\mathbf{B}$ be real matrices with $\mathbf{A}\overset{\mathrm{SVD}}{=}\mathbf{U}_A \mathbf{S}_A \mathbf{V}_A^\mathrm{T}$. I want to maximize \begin{align} \max_B \mathrm{trace}(\...
user avatar
3 votes
0 answers
1k views

Computational complexity of the Cholesky factorization

According to the Cholesky factorization on Wikipedia, the computational complexity of it is $\frac{n^3}{3}$ FLOPs where $n$ is the size of the considered matrix $\mathbf{A}$. There are various ...
actlee's user avatar
  • 376
3 votes
0 answers
164 views

Decomposition of a dense matrix into $m$ tridiagonal matrices

Given an $n\times n$ dense matrix $\mathbf{K}$, is there any decomposition that factorizes $\mathbf{K}$ into $m$ tridiagonal matrices such that $\mathbf{K} = \mathbf{B}_1 \, \mathbf{B}_2 \, \mathbf{B}...
Brian's user avatar
  • 31
3 votes
0 answers
303 views

Is QR factorization continuous?

I can find sources on the internet that provides expression of the derivative of $Q$ and $R$ with respect to $A$ in the expression $A=QR$. One such example is https://j-towns.github.io/papers/qr-...
LudvigH's user avatar
  • 360
3 votes
0 answers
85 views

How calculate the singular values of the Neumann series $M=\sum_{n=1}^\infty A^n$?

Given a matrix $A$, the Neumann series https://en.wikipedia.org/wiki/Neumann_series is defined as $$M=\sum_{n=0}^\infty A^n.$$ For a converge $M$, how to calculate the singular value? Is it possible ...
maple's user avatar
  • 2,883
3 votes
0 answers
40 views

Finding the inverse of the eigenvectors matrix

Hi I have the following $n\times n $ matrix: $$\left(\begin{array}{cccccc} 0 & 0 & 0 & 0 & & -0.5\\ 0.5 & 0 & 0 & 0 & & -0.5\\ 0 & 0.5 & 0 & 0 &...
Daniel's user avatar
  • 105

1
2 3 4 5
20