2
votes
0answers
80 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
1answer
88 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
3answers
298 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
1answer
78 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
0answers
94 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
2answers
618 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 ...
4
votes
1answer
588 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
1answer
148 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
0answers
192 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
1answer
491 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
1answer
299 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} ...
4
votes
1answer
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 ...
5
votes
3answers
443 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
0answers
254 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
2answers
501 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
2answers
618 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
1answer
694 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
2answers
544 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
2answers
814 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 ...
5
votes
1answer
471 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
1answer
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 ...
4
votes
1answer
697 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
0answers
261 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
2answers
739 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
2answers
191 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
2answers
194 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 ...
3
votes
1answer
534 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
4answers
759 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
1answer
625 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
3answers
247 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
3answers
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
1answer
596 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
1answer
473 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
2answers
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
1answer
637 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
0answers
374 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
0answers
340 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
2answers
546 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
2answers
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
0answers
192 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
3answers
544 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
1answer
614 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
2answers
2k 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
1answer
701 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
3answers
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 ...
14
votes
8answers
2k 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 ...
12
votes
3answers
2k views

Analytical formula for numerical derivative of the matrix pseudo-inverse?

Is there a simple numerical procedure for obtaining the derivative (with respect to $x$) of the pseudo-inverse of a matrix $A(x)$, without approximations (except for the usual floating-point ...
0
votes
2answers
828 views

approximate matrix diagonalization algorithm

hello. I am looking for an approximate diagonalization method. I need method which can generate orthogonal transformation to reduce off diagonal elements, but not necessarily make them zero. my ...
1
vote
0answers
1k views

Covariance matrix formula interpretation - what am I missing?

I'm reading a paper that outlines the calculation of a covariance matrix like the following: $C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$ What is the order of this matrix? My interpretation ...
1
vote
2answers
1k views

The Application of Lanczos Algorithm on Sparse Matrix

I am looking for suitable algorithm to compute the eigenvalues and eigenvectors of a matrix. My matrix is sparse ( think of Finite Element Matrix), and it is very, very big ( think of hundreds of ...