Questions tagged [matrices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
46 votes
8 answers

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 ...
Lev Reyzin's user avatar
  • 12k
24 votes
1 answer

Space complexity of Coppersmith–Winograd algorithm

Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$ which is the best ...
Shiva Kintali's user avatar
20 votes
4 answers

Positive topological ordering, take 3

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix? This question is motivated by this problem: Positive topological ordering ...
domotorp's user avatar
  • 13.8k
26 votes
1 answer

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 ...
Joel's user avatar
  • 497
16 votes
2 answers

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 ...
Ho Yee Cheung's user avatar
11 votes
2 answers

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 ...
Lihong Li's user avatar
  • 111
11 votes
1 answer

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 ...
Dimitris's user avatar
  • 1,346
7 votes
2 answers

Complexity of a variant of the max word problem. NP-complete?

I'd like to be able to state that the following problem is NP hard. I am wondering whether anybody have any pointers to related/recent work? The problem: Given a finite set of transition matrices $A$ ...
Al-Mousa's user avatar
4 votes
0 answers

Approximating Front Size of Asymmetric Matrices

The front size of a matrix $A$ is the largest number of non-zeros below the diagonal in any column of its Cholesky factor. If $A$ is symmetric then the minimum front size of $A$ is equal to the ...
Shiva Kintali's user avatar