# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

227 questions
Filter by
Sorted by
Tagged with
332 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 ...
207 views

570 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 ... 4k 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 ...
295 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 ...
40k 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 ...
4k 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 ...
376 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 ...
120 views

### Determinants and bilinear forms

If one calculates the product of diagonal elements of the $U$ matrix in a $LUP$ factorization of a given matrix $A$, one can calculate the determinant of $A$. Also it is known that $LUP$ factorization ...
21k 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 ...
137 views

### Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound

I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are ...
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 ...