All Questions
18 questions
-3
votes
1
answer
145
views
Finding a non-negative solution to an integer system of linear equations
Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
- 215
0
votes
1
answer
43
views
Decomposing outer product or general rank factorization over $\Bbb F_q$
Given matrix $M\in\Bbb F_q^{n\times n}$ with the promise that there are two matrices $A\in\Bbb F_q^{n\times 1}$ and $B\in\Bbb F_q^{1\times n}$ such that $AB=M$ is there a deterministic $O((n\log q)^c)$...
- 13.3k
7
votes
1
answer
275
views
Using an oracle to find a vector $b$ for which $Ax=b$ has a solution
There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as ...
- 233
6
votes
1
answer
225
views
Checking properties of matrices
Given a sparse matrix $A$ in $\mathbb{Z}^{n\times n}$, how easily could one check whether a coefficient $\alpha_k$ of the characteristic polynomial $P_A$ of $A$ is equal to $0$ (without the need to ...
- 73
1
vote
0
answers
187
views
How to efficiently generate a random 0-1 matrix of a given rank
How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?
- 73
2
votes
1
answer
500
views
Matrix multiplication with transpose
Let $A,B\in\mathbb{F}^{n\times n}$ be two $n\times n$ matrices over
the underlying field $\mathbb{F}$. In addition, $A$ is guaranteed
to be a symmetric matrix, i.e, $A=A^{T}$. We assume complexity ...
- 727
4
votes
1
answer
590
views
Rate of convergence for the Perron–Frobenius theorem
The Perron–Frobenius Theorem states the following.
Let $A = (a_{ij})$ be an $n \times n$ irreducible, non-negative matrix ($a_{ij} \geq 0, \forall i,j: 1\leq i,j \leq n$). Then the following ...
- 1,601
2
votes
0
answers
283
views
Running time of Jacobi vs Golub-Kahan for SVD
For an $m \times n$ matrix, what is the running time for computing the Singular Value Decomposition (SVD for short) via
Jacobi's method, and
Golub-Kahan?
The source I read mentions that Jacobi's ...
- 121
7
votes
0
answers
578
views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
- 517
22
votes
3
answers
798
views
Bigger picture behind the choice of matrices in the Strassen algorithm
In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the ...
user4292
10
votes
1
answer
427
views
What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?
I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.
- 2,531
17
votes
2
answers
442
views
similar matrices
Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
- 1,311
11
votes
1
answer
489
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,356
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
9
votes
0
answers
572
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 ...
user4292
8
votes
1
answer
302
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 ...
- 233
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
48
votes
8
answers
22k
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 ...
- 12k