Stack Exchange Network

Stack Exchange network consists of 174 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

{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

10
votes
1answer
202 views

Decide if a matrix is transposable

A matrix $M$ is called transposable if it can be transformed into its transpose $M^t$ via row and column permutations. Is there an efficient a way/algorithm to decide if a given matrix is ...
1
vote
1answer
72 views

Closed Form Solution for Optimization Problem over the Space of Rigid Transforms

Is there a closed form solution to this constrained optimization problem: \begin{equation} \min_{R \in SO(3),\, \mathbf t \in \mathbb R^3} = \sum_{i = 1}^N \| M_i(R \mathbf p_i + \mathbf t) \|^2, \...
0
votes
1answer
80 views

Matrix equation of the form $C A C^\intercal = D$

Consider the following square matrix \begin{align} A = \left(\matrix{d & 0 & -\frac12 & 0 & 0 & 0 & 0 & 0 \\ 0 & d & -d+1 & -\frac12 & 0 & ...
0
votes
0answers
25 views

Kronecker sum matrix for a singular matrix pencil

The Kronecker sum of two matrices $A \in \mathbb{R^{n \times n}}$ and $B \in \mathbb{R^{m \times m}}$ is defined by the matrix. $$A \oplus B = A \otimes I_m + I_n \otimes B \in \mathbb{R^{mn \...
2
votes
0answers
79 views

An inequality concerning the solution of a Lyapunov equation

Let $A$ be an Hurwitz stable matrix (i.e. the real part of the eigenvalues of $A$ lie in the left-half plane) and $Q$ be a positive semidefinite matrix ($Q\ge 0$, for short). Let $P>0$ be the ...
6
votes
1answer
115 views

Any convergence rule for ${\mathbf X}_k={\mathbf A}{\mathbf X}_{k-1}{\mathbf B}$?

We know iteration ${\mathbf X}_k=\mathbf{A}{\mathbf X}_{k-1}$ converges if the spectral radius of $\mathbf A$ is smaller than 1 (see here). Is there any known rule for iteration ${\mathbf X}_k={\...
0
votes
1answer
62 views

Computing spectrum of convex combination of SPD matrices given individual spectral decompositions

Given the spectral decompositions of a non-commuting collection of symmetric positive definite $N\times N$ matrices $$\left\{ K_{i}\right\} _{i=1}^{M}, U_{i}D_{i}U_{i}^{T}=K_{i},\quad i=1,\dots,M,$$ ...
1
vote
1answer
81 views

Lanczos algorithm for finding $k$ smallest eigenvector

I am trying (and have been recommended) to use the Lanczos algorithm to find the $k$ smallest eigenvectors. However, all of the literature seems to talk about this algorithm as a way to estimate the $...
7
votes
1answer
134 views

Is there any sort of higher-order SVD (quadratic and above) for dimensionality reduction?

(Posted this on math.stackexchange and cross.correlated over more than a week ago, but didn't get an answer, and this is a question in my research so this seems like it might have been the better ...
4
votes
1answer
140 views

Is there a fast algorithm to test positivity of all principal minors of non-symmetric matrix?

I have a matrix $A \in \mathbb{R}^{n \times n}$ with positive eigenvalues. In the symmetric case, Sylvester's criterion implies that all the principal minors are positive. In the non-symmetric case, ...
5
votes
1answer
123 views

Numerical minimization spectral norm under diagonal similarity

This question is a follow up. Let $A$ be a real square matrix of size $n \times n$. How to determine the minimum spectral norm under diagonal similarity, i.e., $$ s(A) = \inf_{D} \lVert D^{-1} A D\...
1
vote
0answers
53 views

Calculation of $\chi^2$ for very small covariance matrices

I produced simulations of data for my experiments, changing each time my initial parameter $\theta$ , $n$ times: $\theta_1\, \theta_2, \cdots \theta_N$. For each realisation of my data I calculated ...
0
votes
0answers
29 views

Unstable convergence of a Poisson equation

What could be the reason that the solution of a Poisson equation is smooth when obtained by an iterative solver, only if the maximum residual is set to a high value (e.g. 0.1)? When the maximum ...
0
votes
1answer
222 views

Cholesky decomposition – non-positive definite matrix

In order to pass the Cholesky decomposition, I understand the matrix must be positive definite. However, I also see that there are issues sometimes when the eigenvalues become very small but negative ...
11
votes
0answers
165 views

Fast computation of matrix product $AXA^T$ with fixed $A$?

Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...
0
votes
0answers
128 views

Smallest eigenvalue of a sparse matrix (updated)

Let $D_{1}$ be $(m-1)n \times mn$ matrix (that is, $(m-1)n$ rows and $mn$ columns) and $D_{2}$ be $m(n-1) \times mn$ defined as $$\begin{cases} D_{1}[(m-1)(j-1)+i ; m(j-1)+i] & = -1 , \\ D_{1}[(m-...
7
votes
1answer
187 views

Square root of a large sparse symmetric positive definite matrix

I am trying to calculate $$Y = A^{\frac 12} X$$ where $A$ is a very large and sparse positive definite matrix, say, $10^4 \times 10^4$. Matrix $X$ is known and, say, $10^4 \times 100$. Is there any ...
0
votes
0answers
45 views

Change of polynomial eigenvalues between polynomials

Given the polynomial eigenvalue problem $$ p_t(z) = det ( P(z) + Q(t) ) = 0, $$ where $P(z) = \sum_{i=0}^k P_i z^i$ with $P_i \in \mathbb{C}^{n \times n}$ and $Q(t) \in \mathbb{C}^{n \times n}$. The ...
1
vote
1answer
96 views

Compute the eigenvectors corresponding to the $k$ smallest eigenvalues w.r.t high dimensional symmetric sparse matrix?

So far as I know: The power iteration method can only get the eigenvector corresponding to the largest eigenvalue; The inverse power iteration method requires that the matrix is invertible; The QR ...
2
votes
1answer
116 views

Efficient algorithm for solving a convex quadratic program [duplicate]

Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently? $$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$
4
votes
1answer
112 views

Solving a system of linear equations over the integers

I have a matrix with integral entries $A$ and integer vector $b$, and want to determine if there is exactly one vector $x$ such that $Ax=b$. $A$ is rectangular, and I know there always is a solution. ...
3
votes
1answer
68 views

Numerical iterative methods for Poisson equation

Given a domain $\Omega \subset \Bbb R^n$ and $\Delta\varphi=f$ where $\varphi:\Bbb R^n \to \Bbb R$ is unknown and $f:\Omega\to \Bbb R$ is a blackbox function (for each $\bf x$ it provides $f({\bf x})$,...
2
votes
1answer
114 views

Quadratic matrix equation for $X\in \mathbb{C}^{ n\times p}$ with Hermitian parameters

Let $A\in \mathbb{C}^{ n\times n}$ and $B \in \mathbb{C}^{p \times p}$ be Hermitian matrices with $p < n$. Find matrix $X$ such that $X^*AX=B.$ Solution in the case of positive definite $A$ and $...
7
votes
3answers
230 views

Checking positive semi-definiteness of integer matrix

Key Problem : Is there any theorem about eigenvalues or positive semi-definiteness of small size matrices with small integer elements? I have to check positive semi-definiteness of many symmetric ...
1
vote
0answers
15 views

Empirical approaches to validate observational bounds on minimum gap between least eigenvalues of $n \times n$ correlation matrix and its submatrices

Let $\Sigma$ be an $n \times n$ correlation matrix whose least eigenvalue is denoted by $\lambda$. $\Sigma_i'$ be an $(n-1) \times (n-1)$ submatrix of $\Sigma$ obtained by eliminating the $...
2
votes
0answers
32 views

Partitioning $n$-space based on linear combinations

I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
7
votes
2answers
207 views

Linear equations with absolute values

Assume we have a set of equations in $x \in \mathbb{R}^n$ $$|a_i\cdot x|=b_i$$ where $a_i \in \mathbb{R}^n$ and $b_i>0$ are given. Could such a system be solved efficiently? In a theoretical ...
4
votes
0answers
125 views

Using Linear Programming as an iterative procedure

Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
5
votes
1answer
330 views

In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?

In a large (possibly above $5000\times 5000$) matrix, the problem of finding all the eigenvalues and eigenvectors can be solved using iterative methods (Arnoldi, Lanczos etc.). However, there seems to ...
4
votes
0answers
272 views

Generate non-negative linear combinations of non-negative vectors with different supports

(I will not be surprised if this problem has been solved and/or has a trivial solution – I just do not know the right terminology to google for it.) So the problem is as follows. I have an $m \...
1
vote
0answers
42 views

smallest singular value over invertible sub-matrices

Consider the matrix $M = \begin{bmatrix} A & A B \end{bmatrix} \in R^{n \times (n+m)}$, with $A \in R^{n\times n}$, $B \in R^{n \times m}$, $m < n$, $m > 1$, $A$ symmetric positive definite. ...
0
votes
0answers
181 views

Conjecture about matrix systems of integer solution sets [duplicate]

Consider for all $i,j$ belong to $\Bbb N$ ; $a(i,j)=((2^{(i+1)}+1)^{(j-1)}+1)/2$, then for all $n$ belong to $\Bbb N$ ; the solution set of the matrix system $[a(i,j):1\leq i\leq n, 1\leq j\leq (1+...
1
vote
1answer
121 views

Laplace equation, medium discontinuity and finite difference method

The main question is: How to deal with the Poisson equation in the presence of the medium interface. Let's say we have 1D Laplace equation: \begin{equation} -\frac{d}{dx}\left(\epsilon(x)\frac{d}{dx}\...
7
votes
0answers
142 views

A special eigenvalue problem

For my research I need to solve a generalised eigenvalue problem $Ax=\lambda B x$, where $A$, $B$ are general matrices, and selectively find only eigen-pairs $\lambda, x$ such that $\lambda\in \mathbb{...
2
votes
0answers
30 views

Coarse grid correction

Let $A_h \in \mathbb{R}^{n \times n}$ be the matrix corresponding to a finite element discretization of some nonselfadjoint, bounded and indefinite bilinear form corresponding to a second order ...
4
votes
0answers
95 views

Zero diagonal nonsymmetric block checkerboard matrix: orbits and numerical ranges

Let $A \in \mathbb{R}^{m \times m}$ be a nonsymmetric zero diagonal matrix with a zero/non-zero pattern which is symmetric and persymmetric (i.e. symmetric in the northeast-to-southwest diagonal). If ...
1
vote
1answer
55 views

Solving Linear System with Noisy Input

I have the following triangular system \begin{equation} \begin{pmatrix} 1 & & & & \\ \mu_1 & 2 & & & \\ \mu_2 & \mu_1 & 3 & \\ \...
1
vote
0answers
376 views

What is the time complexity of the largest singular value and its vectors?

Full zero-error SVD on an $m \times n$ matrix $A$ would cost $O(\min(m^2n,mn^2))$. What is the time complexity if we need only the largest singular value and its corresponding vectors? I think it is $...
3
votes
1answer
194 views

Numerically solving for pseudo inverse of non-squared Vandermonde matrix

I have a linear system to solve, set up as: $\bf{Ax}=\bf{b}$ with a non-squared matrix A, $ \bf{A}= \begin{bmatrix} 1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\ 1 & A_{2} & A_{...
0
votes
0answers
498 views

Symmetric positive definite matrix with small condition number

When constructing a symmetric positive definite matrix $A$, it is desirable to have the condition number $\kappa(A)$ be as small as positive. The question: is there a set of rules for matrix ...
1
vote
1answer
893 views

Is the square root of a matrix unique? [closed]

I know the answer is No, since you can put plus/minus on each eigenvalue. But how about putting a psd requirement? Like $A = S^2$, $S$ is psd, is $S$ unique? I was worried about the case where if $\...
4
votes
0answers
343 views

Determining whether a Schur complement is invertible

Consider the symmetric matrix $$M = \begin{bmatrix} A & B \\ B^T & -C \end{bmatrix}$$ where $A \in \cal{R}^{n \times n}$ and $C \in \cal{R}^{m\times m}$ are symmetric, ...
1
vote
0answers
224 views

Condition number of the product of two matrices

Consider two matrices $A$ and $B$ that are non-square in general and may not be full rank. Assuming their shapes are such that the product $A\cdot B$ is well-defined, what is the relationship between ...
3
votes
2answers
314 views

Lower bounds for the singular values of submatrices of othogonal matrices

Let $A$ be an $m \times n$ matrix, $m\geq n$, and let $A=U\Sigma V^T$ be its singular value decomposition. Let us partition $A$ as $A=(A_1|A_2)$, where $A_1$ is of size $m \times k$, and all columns ...
1
vote
1answer
90 views

error bound for least square minimization

Let $X = [x_1 \cdots x_N] \in \mathbb{R}^{d \times N}$ and $ T= [t_1 \cdots t_N] \in \mathbb{R}^{1 \times N}$. Define $$ E(w) = \text{tr}(T - w^TX)(T - w^TX)^T $$ as least square energy. When ...
0
votes
1answer
101 views

How to show inconsistency of a linear system of equations? [closed]

Consider the (real) linear system of equations $A\mathbf{x}=\mathbf{c}$ of size $N$ as $$ \begin{bmatrix} a_{N}-a_{2}& a_{2}& 0 &\dots& 0 & -a_{N} \\-a_{1} & a_{1}-a_{3}&a_{...
3
votes
2answers
175 views

Question about preconditioning

I posted the following question on stackexchange but didn't get any replies; I'm hoping perhaps someone can help me here. I understand that for many iterative methods, convergence rates can be shown ...
3
votes
3answers
338 views

Is this inequality involving the Frobenius norm right?

Let $A$ be a generic (or varying) square, real $ n \times n$ matrix. Let $G$ be a fixed $n \times k$ matrix, $k < n.$ Denote by $||.||_F$ the Frobenius norm. Is it true that $||AG||_F \geq c(G) ||...
8
votes
1answer
273 views

When are two binary matrices simultaneously equivalent to their transpose?

For any real square matrix $A$ there is an invertible matrix $P$ such that $A^t = P^{-1}AP$. I have two binary ($0,1$) matrices $A$ and $B$. When does there exist a $P$ such that $A^t = P^{-1}AP$ and $...
7
votes
2answers
857 views

How can one construct a sparse null space basis using recursive LU decomposition?

Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...