# Questions tagged [numerical-linear-algebra]

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

297
questions

0
votes

0
answers

64
views

### When can a point be reconstructed from relative angle measurements?

Given a set of points $p_1,\dots,p_n$ in $\mathbb{R}^d$ and a target point $x\in\mathbb{R}^d$, I measure all the angles between all pairs of points and the target point. In other words, I have the ...

2
votes

1
answer

121
views

### Is it possible to solve this kind of quadratic simultaneous equations?

$$\mathbf{x} = (x_1, x_2, ..., x_N)^T \in \mathbb{R}^{N} \\
\mathbf{A}_i \in \mathbb{R}^{N \times N},
\mathbf{b}_i \in \mathbb{R}^N ,
\mathbf{c}_i \in \mathbb{R}\\
\mathbf{x}^T\mathbf{A}_i\mathbf{x}...

2
votes

1
answer

246
views

### Usage and origin of the terms dictionary and atom in compressed sensing

In compressed sensing two terms or perhaps fancy word are frequently encountered. One is the dictionary and the other is atom. The dictionary is the matrix and its columns are called "atoms" ...

18
votes

0
answers

268
views

### Why does the random shift in the QR eigenvalue algorithm work in the non-symmetric case over the complex field

I tried to implement the QR algorithm for non-symmetric matrices with complex entries to show to my students. The main part of the implementation was standard: the Householder reduction to the ...

2
votes

0
answers

66
views

### Characteristics of conjugate gradients' iterations for a matrix with clustered spectrum

I am interested in solving
\begin{equation}
Ax = b
\end{equation}
for a large sparse linear symmetric positive definite matrix $A$ by Conjugate Gradients method. (These systems usually come as ...

4
votes

1
answer

289
views

### rank of an integer valued matrix

I make some numerical experiments, involving rank of integer valued matrices of the size about $14\times 24$. As the matrix is integer valued, theoretically there should be no room for errors. However ...

1
vote

1
answer

164
views

### Nearest Kronecker product to sum of Kronecker products

I am interested in efficiently finding the closest Kronecker decomposition to the sum of $k$ Kronecker products:
$$\min_{A,B} || A \otimes B - \sum_{i=1}^k A_i \otimes B_i ||_F$$
where $A,A_i$ are $p \...

1
vote

0
answers

92
views

### Vandermonde-type factorization of moment matrix?

Consider $n,d \in \mathbb{N}_{>0}$, there are many functions $y:\mathbb{N}^{n} \to \mathbb{R}$. Now for simplicity, we denote $y(\alpha)$ to be $y_{\alpha}$. Let $|\alpha| = \sum_{i=1}^{n}\alpha_{i}...

1
vote

0
answers

67
views

### Reference request: finding entries that prevent matrix from being correlation matrix

I am currently doing some research with a quantitative finance firm and my supervisor has raised an interesting question that shows up a lot with their clients: quite often, clients will want to do ...

0
votes

0
answers

56
views

### Concentration of bilinear forms

This is a bit vague so I'll begin by indicating the motivation. I am looking for ways to [do something interesting or useful] with the self-attention in transformer models. Ultimately the self-...

1
vote

0
answers

72
views

### Computing smallest singular value of a matrix with explicit error control?

Many good algorithms are out there computing truncated SVD: What is the time complexity of truncated SVD?.
I am trying to implement some codes to find the smallest singular value of a big matrix $A$. ...

0
votes

1
answer

79
views

### Matrix quantization and effect on singular values

Let $A$ and $B$ be an $N\times n$ matrix with $n\le N$, and let $\sigma_1(X),\dots \sigma_n(X)$ denote the singular values of $X\in \{A,B\}$. Do we have upper and lower bounds for
$$
\|
\sigma_i(A)-\...

0
votes

0
answers

27
views

### The selection of minimal generating sets in Lie algebra

Suppose $A$ is a Lie algebra on field $F_{p}$ with $[A,A,A]=0$. Denote $\{a_{1},\cdots,a_{d}\}$ is a minimal generating set of $A$.It's possible that $[a_{i},a_{j}]=0$ for some $1\leq i<j\leq d$ ...

7
votes

1
answer

234
views

### Efficiently solve the Sylvester equation $AX+XA = C$ where $X$ is skew-symmetric

Is there a way (more efficient than the standard vectorization) to solve the following Sylvester equation in the skew-symmetric matrix $X$ $$AX+XA = C$$ where the matrix $A$ is symmetric positive ...

1
vote

0
answers

177
views

### Connection of eigenspace of finite Hilbert matrix and its continuous operator counterpart

I am trying to understand the connection between the eigenspace of the continuous operator
$$
H(x,y) = \frac{1}{x+y}
$$
which is nothing but the square of the Laplace operator, and its discrete ...

2
votes

1
answer

113
views

### Cosine-sine decomposition yields zero diagonals

I have implemented the Cosine-Sine decomposition of a square matrix in Mathematica. That is, for a given matrix $U$ (where in my use-case, $U$ is unitary) with equally-sized partitions
$$
U = \begin{...

2
votes

2
answers

209
views

### Theoretical/Practical Implications of DFT Eigenvectors

Discrete Fourier transform (DFT) has only four distinct eigenvalues: $±1$ and $±i$. For large matrices , each eigenvalue $λ$ yields a multidimensional eigenspace, allowing linear combinations of ...

3
votes

1
answer

232
views

### Inflection point calculation for cubic Bézier curve encounters division by zero

I've been working on finding the inflection points of a cubic Bezier curve using the method described in a paper Hain, Venkat, Racherla, and Langan - Fast, Precise Flattening of Cubic Bézier Segment ...

2
votes

1
answer

158
views

### How to do LU factorization efficiently based on the factorized result added with a low-rank matrix?

Suppose a square $n\times n$, dense matrix $A^{\text{old}}$ has been factorized into $L^{\text{old}}$ and $U^{\text{old}}$ components by performing a LU decomposition $A^{\text{old}} = L^{\text{old}}U^...

0
votes

0
answers

27
views

### How can one orthogonalize the pointwise sum of two orthogonal sets?

Let $n = 2k$, and suppose that $V = \{v_1, \cdots, v_k\}$ is an orthogonal set in $\mathbb{R}^n$. In other words, the vectors in set $V$ are pairwise orthogonal to each other.
Now, consider a new set $...

0
votes

2
answers

125
views

### Reshaping data vector into a matrix for deconvolution using a circulant matrix

Suppose we have a circulant matrix S made from pseudorandom binary sequence of length $N$ consisting of $0$'s or/and $1$'s. $1$ means that we can inject something for chemical analysis and $0$ means ...

5
votes

0
answers

199
views

### Difficulty of solving $Ax=b$ in terms of limiting spectral density of $A$?

Suppose $A$ is a random real-valued $n\times n$ matrix and we want to know the difficulty of solving $Ax=b$ when entries of $b$ are sampled IID from Normal$(0,1)$.
Can we say anything about the ...

0
votes

0
answers

91
views

### Efficient method to determine minimum eigenvalue of $2 \times 2$ block diagonal matrix

Suppose $H$ is a $2 \times 2$ block-diagonal symmetric matrix in $\mathbb{R}^{2^N \times 2^N} $. That is
$$ H = \begin{pmatrix} A_1 & 0 & \cdots & 0\\ 0 & A_2 & \cdots & 0 \\
...

1
vote

0
answers

58
views

### Backward stability of the SVD

I am interested in the backward stability of numerical algorithms for computation of the singular value decomposition (SVD). Specifically, I am interested in the following result:
Backward stabile ...

1
vote

0
answers

322
views

### The geometrical multiplicity of the nilpotent matrices

The following point is well-known in the literature.
Theorem. Let $A$ be a non-negative matrix in $M_n(\mathbb{R})$. If $A$ is nil-potent, there is a permutation matrix $P$ such that $P^tAP$ is ...

1
vote

1
answer

61
views

### Characterization of the behavior of the residuals in conjugate gradient

In conjugate gradient method for solving symmetric positive definite linear system $Ax=b$, which can also be regarded as a convex optimization problem $\dfrac{1}{2} x'Ax - x'b$, the $A$-norm of the ...

1
vote

0
answers

155
views

### QR algorithm for eigenvalues and eigenvectors of large symmetric matrices

I am trying to write a QR algorithm in Python for eigenvectors and eigenvalues finding for large symmetric matrices,
My initial thought was to use Householder transformation with a Wilkinson shift ...

34
votes

3
answers

3k
views

### Quickly determining if a matrix has any PSD completion

Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?
Slightly more precisely: for simplicity let's assume ...

3
votes

0
answers

229
views

### Efficient way to calculate Smith Normal Form of large integer matrices

I am interested in calculating the Smith Normal Form for Laplacian matrices of hypercube graphs. Using the elementary divisors method from SAGE, I was able calculate up to the 11-cube (which has a $2^{...

1
vote

0
answers

125
views

### Generalized eigenvalues of block matrix

Let $A, D \in \mathbb{R}^{n\times n}$ be symmetric matrices and consider the following matrix pencil
$$
\begin{pmatrix}
-I & A+\lambda I \\
A+\lambda I & -D \\
\end{pmatrix}
$$
If we already ...

3
votes

0
answers

283
views

### efficient numerical algorithm for matrix determinant

It appears that in numerical analysis the question of computing the determinant $\det A$ of a real or a complex $n\times n$ matrix $A$ is not well-studied, and a usual recommendation is to use matrix ...

2
votes

1
answer

301
views

### Linear system with sum of Kronecker products

Here and here, specific ways to address the equation in $x$, for $N=2$, are given:
$$\sum_{i=1}^N (A_i\otimes B_i)x=c$$
Is anything know about the case $N>2$?
I am looking in fact for an efficient ...

30
votes

2
answers

1k
views

### Gaussian elimination is just Gram-Schmidt with a change to the inner product symbol?

I noticed at some point that if you take the Gram-Schmidt algorithm for taking the QR decomposition of a matrix, and you change the meaning of the inner product symbol $\langle \mathbf u, \mathbf v \...

3
votes

1
answer

269
views

### Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries

I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...

1
vote

0
answers

18
views

### Optimal Truncation of LDL-factorization to improve conditioning

Suppose I factored real symmetric quasi-definite $ A_0= L_0 \cdot D_0 \cdot L_0^T$ and the factorization exists, with $D$ diagonal and $L$ unit lower-triangular; and suppose $L$ and $D$ are badly ...

1
vote

0
answers

34
views

### Slope assertion in Cholesky on digital computers

For a real symmetric positive definite linear system
$$ A \cdot x = b, $$
solved using Choelsky with forward- and backward-substitution, we know it for the numerical approximation $\tilde{x}$ to $x$ ...

3
votes

2
answers

236
views

### Practical symmetric equivalent to QR factorization updates

As we know, the QR-factorization $Q\cdot R=A$ of any real symmetric $n \times n$ matrix $A$ with full rank is unconditionally numerically stable. Further, when A is rank-1-updated, the factorization ...

6
votes

2
answers

448
views

### Spectrum of operator involving ladder operators

The ladder operator in quantum mechanics are the operators
$$a^\dagger \ = \ \frac{1}{\sqrt{2}} \left(-\frac{d}{dq} + q\right)$$
and
$$a \ \ = \ \frac{1}{\sqrt{2}} \left(\ \ \ \!\frac{d}{dq} + q\...

1
vote

1
answer

255
views

### Eigenvalues of a circulant: DFT or Inverse DFT Convention?

Currently, most engineering texts (and webpages including Wikipedia) define forward discrete Fourier transform with a negative sign on the exponential. This is a convention and the inverse discrete ...

1
vote

1
answer

352
views

### Extracting eigenvalues of a circulant matrix using discrete Fourier matrix

The eigenvalues of a circulant matrix $C$ can be extracted as $$
\Lambda=F^{-1} C F
$$
where the $F$ matrix is a discrete Fourier transform matrix and $\Lambda$ is a diagonal matrix of eigenvalues.
...

3
votes

1
answer

181
views

### The proof of the invertibility of $\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$

Suppose that $n$ is even. Any suggestion/appraoch to prove that $S=\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$ is invertible?

1
vote

0
answers

134
views

### What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^{\frac{n-1}{2}}$ when $n$ is odd?

Suppose that $n$ is odd. The eigen values/eigenvectors of the skew-circulant matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ are successfully computed in this post.
Q. What are ...

3
votes

1
answer

355
views

### The eigenvalues of the matrix $\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$

What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ when $n$ is odd?

1
vote

1
answer

114
views

### Can the condition number of a Jordan basis be made stubbornly large?

For each $k \in \mathbb R$, does there exist a non-empty open ball $B$ of $\mathbb R^{2 \times 2}$ such that for all $M \in B$ and Jordan decompositions $PJP^{-1}$ of $M$, the condition number $\kappa(...

3
votes

0
answers

160
views

### Can the Jordan decomposition of a matrix be computed in a backwards stable way?

Let $PJP^{-1}$ denote the Jordan decomposition of $M$. The matrix $J$ is a direct sum of Jordan blocks; it is unique up to permutation of the Jordan blocks. The matrix $P$ is not unique.
There are two ...

0
votes

0
answers

174
views

### How to analyse the range of eigenvalues of a symmetric and indefinite matrix?

Let $G$ be a symmetric and indefinite matrix defined as follows
$$ G := S - \begin{pmatrix} I_n & I_n \\ I_n & I_n \end{pmatrix},$$
where $S$ is a symmetric positive definite matrix of size $...

1
vote

0
answers

103
views

### Solving a block tridiagonal system with diagonal perturbations

Say we have a block tridiagonal matrix, $T \in \mathbb{R}^{NL \times NL}$, with constant off diagonals, $\mathbf{B} \in \mathbb{R}^{L\times L}$, given by
$$
T = \begin{bmatrix} \mathbf{A}_1 & \...

0
votes

1
answer

73
views

### $\det(HH’) = 0$ for nonnegative $H$

$H$ is an $n\times m$ matrix with non-negative coefficients and $n < m$. $H'$ is the transpose of $H$.
Are the following statements true?
If $\det(HH’) > 0$, the rows of $H$ define the edges of ...

1
vote

1
answer

64
views

### Given a set of vectors how to pick $M$ such that sum of maximums of coordinates is maximized?

I asked the same on math.Stackexchange.
I have $n$ (say $n = 300$) vectors $v_1,\dots,v_n$. Each of them has $K$ coordinates (say $K = 30$). For vector $v_j$ I denote it's coordinates as $v_{j1},\...

1
vote

0
answers

36
views

### Efficient solution to linear matrix equations

A general form for a linear matrix equation can be written as
$$AX + XB + \sum C_iXD_i$$
If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...