# Tagged Questions

**1**

vote

**1**answer

38 views

### Partial Constraint of Low Rank Matrix

Suppose $X \in \mathbb{R}^{m \times n}$ is a rank $r$ matrix. Let $\Omega$ be a generic subset of $\in \{1, \ldots, m\} \times \{1, \ldots, n\}$ of cardinality $r(m + n - r)$. Denote by $X_{\Omega}$ ...

**1**

vote

**1**answer

96 views

### Are there some algorithms to solve the diagonal matrix $X$ to the following matrix equation?

Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the ...

**1**

vote

**1**answer

170 views

### Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation:
$X=c \cdot AXA' - diag(c \cdot AXA')+ I$,
where
(1) $A \in R^{n \times n}$ is a given matrix whose element ...

**4**

votes

**0**answers

103 views

### Rank 1 Approximation of Elementwise Inverse Matrix

I'm wondering whether there is a good way to solve the following optimisation problem.
Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that
$$ \| D_1 A ...

**2**

votes

**0**answers

95 views

### Stationary Distribution for Markov-like system?

Let
\begin{equation}
A=
\begin{pmatrix}
0 & a_{1,2} & a_{1,3} \\
a_{2,1} & 0 & a_{2,3} \\
a_{3,1} & a_{3,2} & 0
\end{pmatrix},
\end{equation}
\begin{equation}
B=
...

**3**

votes

**1**answer

102 views

### Trace of multiplied positive definite matrices

I have to compute $Tr(K^{-1}\Sigma)$ where both $K$ and $\Sigma$ are symmetric positive definite matrices.
Question is considering that I have computed the Cholesky, $L_1$ of $K$ previously, is there ...

**8**

votes

**3**answers

404 views

### Best known bounds on tensor rank of matrix multiplication of 3×3 matrices

Years ago I attended a conference where they taught us that matrix multiplication can be represented by a tensor. The rank of the tensor is important, because putting it into minimal rank form ...

**2**

votes

**1**answer

86 views

### Updating $LU$ decomposition after adding a sparse matrix

How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...

**4**

votes

**0**answers

107 views

### Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D ...

**3**

votes

**2**answers

764 views

### Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...

**5**

votes

**1**answer

656 views

### Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...

**1**

vote

**1**answer

169 views

### integral basis of orthogonal complement

Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$.
My goal is to find an ...

**2**

votes

**0**answers

215 views

### eigenvalues of the sum of a stochastic matrix and a diagonal matrix

Let $D$ be a real diagonal matrix $D=diag(a_1,a_2,\ldots,a_n)$ with $a_1\le a_2\le\ldots\le a_n$. Assume that at least one of the $a_i$ is positive. Let $P$ be an irreducible, real, row-stochastic ...

**4**

votes

**1**answer

531 views

### Matrix perturbation theory

I am having matrix $M_0$ with coresponding eigenvectors and 4 eigenvalues {0,0,a,-a}. Eigenvalue $\lambda=0$ is double degenerated. Now I am appliing small perturbation $\epsilon M_1$ and want to get ...

**4**

votes

**1**answer

318 views

### Norm of inverse confluent Vandermonde matrix

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as
$$V=
\begin{bmatrix}
...

**5**

votes

**1**answer

1k views

### Upper bound on largest eigenvalue of a real symmetric n*n matrix with all main diagonal >0, everywhere else <=0

Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them ...

**6**

votes

**4**answers

571 views

### solving Lyapunov-like equation

The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...

**12**

votes

**0**answers

286 views

### Descartes rule of signs for a noncommutative polynomial in matrix variables

Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is
\begin{equation*}
\mathcal{G}(X) := X^n - ...

**2**

votes

**2**answers

589 views

### sparsity of QR decomposition

Hi, everyone!
I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...

**5**

votes

**2**answers

673 views

### Factorizing a block symmetric matrix

Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.
I would like to ...

**1**

vote

**1**answer

714 views

### On an eigenvalue inequality

Let $\lambda_1 (\cdot)$ be the larger absolute value
eigenvalue of a $2\times2$ matrix and $\lambda_2 (\cdot)$
the smaller absolute value eigenvalue of a $2\times2$ matrix, i.e.
$|\lambda_1 (\cdot)| ...

**2**

votes

**2**answers

554 views

### Eigenvectors of a diagonalizable matrix

Suppose we have a n-by-n symmetric matrix K which can be factorized in a way, K = H * L * H', where L is a m-by-m diagonal matrix and H is a n-by-m matrix. In addition, let's assume n <= m.
Can we ...

**4**

votes

**2**answers

972 views

### Is there some algorithms for solving non-linear matrix equations?

Is there some algorithms for solving non-linear matrix equations on field $\mathbb{C}$?
Especially, solving polynomial nonlinear matrix equations.
For instance, let $X$ be some matrix satisfying
...

**6**

votes

**1**answer

512 views

### Special considerations when using the Woodbury matrix identity numerically.

Are there any special considerations when using the Woodbury matrix identity numerically? What is the best metric for numerical stability in this case? Can anyone point me to a good reference?
The ...

**2**

votes

**1**answer

1k views

### How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) (“mathematicalized reformulation”)

New edition of the question, "mathematicalized" (thanks to Gerhard).
Consider and integer valued n*n matrix M, with integers elements in the range -N < m < N.
I want to find integer-valued ...

**5**

votes

**1**answer

719 views

### Convergence speed of Jacobi eigenvalue algorithm for parallel ordering(Brent-Luk) ?

Is there estimate for convergence of the Jacobi eigenvalue algorithm for Hermitian matrices for "parallel ordring" (Brent-Luk ordering (see comment below)) ?
For example for 4 4 matrices parallel ...

**4**

votes

**0**answers

271 views

### What are the eigenvectors of the Lagrange interpolation matrix?

Let $F$ be a field.
Let $x_1,\ldots,x_k,y_1,\ldots,y_k\in F$ be distinct elements in the field.
Consider the $k\times k$ matrix that in position $i$, $j$ has the element
$\frac{\prod_{l\neq i}(y_i - ...

**5**

votes

**2**answers

836 views

### Solving for Moore Penrose pseudo inverse

I have a system to solve, set up as :
$$Ax = b$$
with a square rank deficient matrix $A$. The paper suggests to use a Moore Penrose pseudo inverse, which in my case can be computed using the ...

**2**

votes

**2**answers

203 views

### Maximization of a matrix product by iterative methods

This might not be very difficult, but I think I may have gotten a little confused.
Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...

**1**

vote

**2**answers

198 views

### How to approx. decompose a sym. p.d. matrix M into X'X?

M: pxp symmetric p.d. matrix with unit diagonals
n: number much smaller than p
Want a nonrandom nxp matrix X such that X'X is
close to M element-wise. If n gets larger, hopefully
difference ...

**4**

votes

**1**answer

581 views

### Cholesky Rank-1 downdate extension

If we have a matrix $K$ we can take do a rank-1 downdate of its Cholesky $L = chol(K)$ to find $L_\star = chol(K - v v^\top)$ in $O(N^2)$ time as opposed to $O(N^3)$ time for doing the Cholesky from ...

**6**

votes

**4**answers

784 views

### How to solve Ax=b incrementally ?

Hi, everyone.
What I am struggling is the following problem. I have a linear matrix equation $Ax=b$, where $A$ is a known $n \times n$ large sparse real matrix, $x$ and $b$ are known $n \times 1$ ...

**6**

votes

**1**answer

662 views

### Arnoldi method to compute the dominant eigenvector

Hi, everyone!
I have a problem of computing the dominant eigenvector. When I want to approximate the dominant eigenvector of a large sparse matrix via the famous Arnoldi method, I am wondering how to ...

**2**

votes

**3**answers

257 views

### is there any efficient way to compute the follow matrix equations easily

Let $A$ and $D$ are $n\times n$ diagnal matrices, and $B$ is an $n\times n$ orthogonal matrix. Is there any efficient way to compute the follow matrix equations easily?
$\sum_{i=0}^{k} A^i \cdot B^T ...

**-1**

votes

**3**answers

1k views

### How to compute the induced $||\cdot||_{2} $ matrix norm of an SPD matrix

Hi, I know they are related questions on the board but mine is more specific. Although the answer for any non-singular matrix would be also interesting. Thanks!
UPDATE: I am sorry I though this ...

**2**

votes

**1**answer

648 views

### Is it possible to decompose a symmetric, positive definite matrix in this way?

Let $\Sigma$ be a symmetric positive definite matrix. Then the Cholesky decomposition gives us $\Sigma=LL'$ where $L$ is lower triangular and unique.
Under what conditions (if any) does there exist ...

**0**

votes

**1**answer

522 views

### randomized SVD singular values

randomized SVD decomposes a matrix by extracting the first k singular values/vectors using k+p random projections.
my question concerns the singular values that are output from the algorithm. why ...

**0**

votes

**2**answers

2k views

### Square root of non-positive definite matrix

Finding square root of matrices using Cholesky decomposition is limited to positive definite matrices. Any other method to find square root of matrix which has some diagonal values approximately zero ...

**4**

votes

**1**answer

694 views

### Computation of a Drazin inverse

I need to compute the Drazin inverse $A^D$ of a singular M-matrix $A$, i.e., a matrix in the form $A=\lambda I -P$, where $P$ has nonnegative entries and $\lambda$ is the spectral radius (Perron ...

**3**

votes

**0**answers

390 views

### Convergence of the relaxation method for every parameter in the relevant disk

For large size matrices, the resolution of linear systems $Ax=b$ is often done iteratively. The matrix $A$ is split as $A=M-N$, with $M$ invertible, and one performs
$$x^{k+1}=M^{-1}(Nx^k+b).$$
The ...

**4**

votes

**0**answers

360 views

### The order of the Jacobi method for Hermitian matrices

Let $H$ be an $n\times n$ Hermitian matrix. The Jacobi method is an iterative method for finding the spectrum of $H$. It is described in every book on numerical linear algebra.
Principle: At step ...

**6**

votes

**2**answers

565 views

### An orthogonal companion matrix

Let $P\in{\mathbb R}[X]$ be a monic polynomial with roots on the unit circle. For the problem below, we may assume wlog that the roots are simple and distinct from $\pm1$. It can be shown that there ...

**2**

votes

**2**answers

3k views

### Computing the largest Eigenvalue of a very large sparse matrix?

I am trying to compute the asymptotic growth-rate in a specific combinatorial problem depending on a parameter w, using the Transfer-Matrix method. This amounts to computing the largest eigenvalue of ...

**2**

votes

**0**answers

194 views

### subspace separation and M-matrices

The separation between two square matrices $A$ and $B$, often used as a measure of the sensitivity of invariant subspace problems, is defined as
$$
\operatorname{sep}(A,B)=\min_{X\neq ...

**3**

votes

**3**answers

596 views

### Conjugate Gradient for a “slightly” singular system.

Suppose I have a symmetric $N \times N$ matrix A which has a one-dimensional Nullspace $N$. A is positive definite on $N^\bot$. In my case $N$ is the space of constant vectors (i.e. generated by ...

**2**

votes

**1**answer

629 views

### Condition number for Ellipsoid method matrix

Hello,
When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$.
...

**5**

votes

**2**answers

3k views

### Is there a way to simplify block Cholesky decomposition If you already have decomposed the sub matrices along the leading diagonal?

Lets say we have a block matrix $ M =\left( \begin{array}{ccc}
A & B\\\\
B^{*} & C \end{array} \right)$ where M is positive definite. (A, and C are also pos def)
There is a formula for ...

**3**

votes

**1**answer

751 views

### Maximize the multiplicity of an eigenvalue

Hi,
We have a real, non-singular and symmetric matrix M of size n by n, with diagonal elements 0's. Its eigenvalues and eigenvectors are computed.
Now we wish to change its diagonal elements ...

**6**

votes

**3**answers

1k views

### minimize the sum of absolute eigenvalues

Hi,
We have a real symmetric matrix M with diagonal elements 0's, the eigenvalues and eigenvectors of M are computed.
Now we wish to change its diagonal elements arbitrarily to minimize the sum of ...

**13**

votes

**8**answers

3k views

### Exponential of large matrices

I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...