# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

191 questions
Filter by
Sorted by
Tagged with
370 views

### norms of compressible and incompressible vector

Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$ I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case ...
110 views

131 views

### Reference request: reducing rank computations to characteristic polynomials over arbitrary rings

Question. I'm looking into certain algorithms for linear algebra which lie in NC2. Does anyone know of alternative references for the proof of the proposition just below, relating rank of matrices ...
2k views

### Definition of matrix-multiplication exponent $\omega$

Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a ...
340 views

### Complexity to calculate a full set of eigenvectors over a finite field

Let a full rank $n\times n$ matrix ${\bf A}$ with elements over $\mathbb{GF}(2)$. What is the worst case complexity to calculate $n$ linearly independent (over $\mathbb{GF}(2)$) vectors, such that ...
798 views

### Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically: Problem. For a given system of $m$ linear ...
564 views

### Can such a matrix exist?

During my work i came up with the following problem: I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties: The determinant of $M$ is even. For ...
1k views

### Complexity of finding the leading eigenvector of a graph Laplacian

Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$? Are there any families of Laplacians for which it takes ...
326 views

### Cases of nearly linear time solvable linear systems

Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$ Solving for ${\bf x}$ through standard Gaussian Elimination ...
193 views

540 views

### Finding SVD efficiently for $AB^T$

I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ and $B$ separately) EDIT: (I have added the second question here since it was closed as a ...
3k views

### Evidence that matrix multiplication can be done in quadratic time?

It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple: What reasons do we have for believing that $\omega = 2$? I'm ...
289 views

### Transitive closure of an affine relation

I am looking for work on computing the transitive closure of an affine relation in the following sense: Let $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ be the relation defined by a system of linear ...
25k views

### What is the actual time complexity of Gaussian elimination?

In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
3k views

### Matrix multiplication in $O(n^2 \log n)$

I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read ...
3k views

### Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix . For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
365 views

### Calculating a fast matrix vector product between vector of reals and a 0-1 matrix

Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $0$ or $1$ coordinates \begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\ V_2=(c_{2,1} ... c_{2,l}),\\ .....\...
1k views

### Survey on algorithms/complexity of linear algebra

I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
14k views

### Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension ...
The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is ...