Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
22
questions
46
votes
8
answers
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 ...
- 11.9k
19
votes
2
answers
2k
views
A data structure for minimum dot product queries
Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
- 1,559
14
votes
2
answers
1k
views
Checking equivalence of two polytopes
Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$.
Furthermore, consider two polytopes
$$\begin{align*}
P_1&=\{(f_1(\vec{x}), \cdots, f_m(\...
- 1,345
26
votes
3
answers
1k
views
Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1
Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\...
user17100
19
votes
1
answer
934
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 equations ...
- 8,821
4
votes
1
answer
427
views
Approximation algorithms for min vector subset-sum over GF(2)
In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum.
Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to ...
- 1,318
97
votes
2
answers
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 ...
- 23.1k
62
votes
4
answers
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 ...
- 803
30
votes
2
answers
879
views
Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?
I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix.
If any one knows if this problem is of a different complexity ...
- 483
26
votes
1
answer
979
views
Complexity of matrix powering
Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:
Is the top-right entry of $M^n$ positive?
Note that the ...
- 497
21
votes
1
answer
793
views
What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?
In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the ...
- 13.5k
19
votes
2
answers
1k
views
What is the space complexity of calculating Eigenvalues?
I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space ...
- 323
19
votes
4
answers
706
views
How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?
Can anyone help me with the following problem?
I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
- 193
19
votes
4
answers
992
views
Checking if all products of a set of matrices eventually equal zero
I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.
This means exactly what ...
- 775
18
votes
3
answers
2k
views
Determinant modulo m
What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but ...
- 343
16
votes
2
answers
7k
views
What is the fastest algorithm to compute rank of a rectangular matrix?
Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?
I am aware it can be solved through linear matroid intersection, which ...
- 163
15
votes
1
answer
3k
views
The minimum number of arithmetic operations to compute the determinant
Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$? For example, $n=5$.
- 3,950
13
votes
1
answer
542
views
Algorithmic Vector Problem
I have an algebraic problem related to vectors in the field GF(2).
Let $v_1, v_2, \ldots, v_m$ be (0,1)-vectors of dimension $n$, and $m=n^{O(1)}$. Find a polynomial time algorithm that finds a (0,1)-...
- 674
11
votes
2
answers
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 ...
- 111
11
votes
1
answer
469
views
Constructing vectors in general position
Let a real $k\times n$ ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.
Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such ...
- 1,346
10
votes
2
answers
518
views
Restricting entries of unitary operators to real numbers and universal gate sets
In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-...
- 3,758
9
votes
3
answers
872
views
Non-Orthogonal Vectors Problem
Consider the following problems:
Orthogonal Vectors Problem
Input: A set $S$ of $n$ Boolean vectors each of length $d$.
Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
- 5,127