Tag Info

Hot answers tagged numerical-linear-algebra

Accepted

• 5,430
Accepted

Minimize spectral radius with orthogonal matrix

For an $n\times n$ matrix, the answer is $$|\det A|^{\frac1n}.$$ Explanation: on the one hand, $\rho(UA)\ge|\det (UA)|^{\frac1n}=|\det A|^{\frac1n}$. On the other hand, singular value decomposition ...
• 51.9k
Accepted

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

Here, we verify the observation of @BrendanMcKay that the eigenvalues are $n$ with multiplicity $(n+1)/2$ and $-n$ with multiplicity $(n-1)/2$. Note that your matrix is skew-circulant, and it is known ...

Solving a system of linear equations over the integers

To make sure I understand: you have an $m \times n$ matrix and vector in $\mathbb{Z}^n.$ Is the system a priori over- or under-determined? The former case is a little easier than the latter, but in ...
• 95.9k
Accepted

Complexity of rectangular matrix multiplication

Assuming that efficient means better than the naive $O(n^{2+k})$ multiplication, let us review some possibilities. Padding. For $k > \omega-2$, just pad $A$ with $n-n^k$ zero or garbage rows, ...
• 4,159

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

I'm not sure how well this will answer the question "why does this happen?" But hopefully will provide more geometric/abstract views of this. It seems to me that the Gramâ€“Schmidt and ...
• 964

Is this inequality involving the Frobenius norm right?

For a short fat matrix $G$ (more columns than rows), $\|AG\|_F \geq \sigma_{\min}(G)\|A\|_F \geq n \sigma_{\min}(G) \|A\|$, where $\sigma_{\min}(G)$ is the least singular value of $G$. This follows ...
• 19.5k
Accepted

When are two binary matrices simultaneously equivalent to their transpose?

Clearly, a necessary condition is that for every word $w$ in two letters, one has $${\rm Tr}\,w(A^t,B^t)={\rm Tr}\,w(A,B).$$ Equivalently, $${\rm Tr}\,\hat w(A,B)={\rm Tr}\,w(A,B),$$ where $\hat w$ is ...
• 51.9k

Is it faster to compute eigenvalues or coefficients of characteristic polynomials?

With the traditional algorithms and complexity measures used in numerical linear algebra (dense real matrices, floating point computations, flop count as a complexity measure), they are both more or ...
• 19.5k

Why is fast matrix multiplication impractical?

Addressing the Boolean part. Usually, fast matrix multiplication relies heavily on the element type being a ring; in particular, that every element has an additive inverse. For example, Strassen's ...
• 4,159
Accepted

rank of an integer valued matrix

Note that if you take a prime $p$ and treat the matrix $A$ as a matrix $A'$ over $\mathbb{Z} / p \mathbb{Z}$, then from the property of $\operatorname{rank}(A)$ being the largest order of a non-zero ...
• 3,049
Accepted

Matrix equation with Hadamard product and its own inverse involved

Removing all unnecessary parameters, we come to the equation $\Omega^{-1}=2 W\odot \Omega + B$ where $B$ is positive definite. We need to find a solution in the cone $M_+$ of positive definite ...
• 60.9k
Accepted

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

On the LUQ decomposition The algorithm implemented in luq (see reference given below) computes bases for the left/right null spaces of a sparse matrix $A$. ...
• 6,025
Accepted

Spectrum of operator involving ladder operators

Q: Does anybody know how to numerically overcome this pseudospectral effect? The key idea is "normal ordering". Rewrite the problem in such a way that annihilation operators $a$ appear to ...
• 183k
Accepted

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

The terms "dictionary" and "atoms" predate compressed sensing, they are more generally used in signal processing. An example is the Gabor atom for wavelets. For an early use of &...
• 183k