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

**10**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**3**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**3**answers

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

**1**answer

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

**2**answers

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 ...