# Tag Info

Accepted

• 690
Accepted

• 2,162

### 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 ...
• 17.7k

### 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 ...
• 93.8k

### 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 ...
• 17.7k
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, ...
• 3,012

### Computation time of Smith normal form in Maple

(Dense) Smith Normal Form is theoretically computable in $O(\|A\| \log \|A\| N^4\log N)$ time (Arne Storjohann, 1996). Storjohann was at Waterloo at the time, so I would not be surprised if that is ...
• 93.8k
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 ...
• 52.9k
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 ...
• 47.5k

### What is the time complexity of truncated SVD?

According to the man page of svds, provided by MATLAB, svds is currently based on "Augmented Lanczos Bidiagonalization Algorithm" when it comes to the top-$k$ SVD computation of a large-...
• 51