The matrices tag has no wiki summary.
6
votes
0answers
151 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, ...
7
votes
0answers
120 views
Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)
I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
3
votes
0answers
47 views
Delocalization of eigenvectors in Expanding Graphs
Given an adjacency matrix A, can we say something about whether the eigenvectors corresponding to its highest(or second-highest) eigenvalues are delocalized ? By delocalization I mean that every ...
2
votes
2answers
139 views
The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers
How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?
15
votes
2answers
239 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 ...
8
votes
1answer
229 views
Can we get a sorted list from a sorted matrix in $O(n^2)$
I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$.
I proceed by assuming that it can be done ...
3
votes
1answer
106 views
What is this matrix column-selection problem, and how hard is it to approximate?
I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place ...
5
votes
1answer
128 views
Effective algorithm of searching the “nearest” doubly stochastic matrix
Given a data matrix $D$, is there any effective algorithm to solve the optimization problem
$\min_Q || D - Q ||_F$
such that
$Qe=e$,
$e^TQ=e^T$, and
$Q_{i,j} \geq 0 $ $\forall i,j$,
where ...
3
votes
2answers
134 views
Fast computation of Frobenius norm under memory limits
Given a large dense matrix $A^{n \times n}$, that does not fit to the memory (RAM). Is there any fast way to compute the exact Frobenius norm of the matrix or its accurate approximation (perhaps, via ...
1
vote
0answers
58 views
Can I apply the constraint while constructing the Lagrangian?
Consider the problem:
$\min_X ||XAX^T||_F$
s.t. $X^TX=I$
If A and X are real matrices, the lagrangian will be $tr(XAX^TXA^TX^T)+\sum_i\alpha_i(x_i^Tx_i-1)+\sum_i\sum_{j\neq i}\beta_{ij} q_i^Tq_j$ ...
4
votes
0answers
146 views
What is computational complexity of calculating the Variance-Covariance Matrix?
I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector ...
8
votes
1answer
262 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.
18
votes
0answers
470 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 ...
9
votes
1answer
151 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 ...
6
votes
1answer
171 views
Discrete log in GL(2,p)
Let $p$ be a large prime. Let $A$ be a $2\times 2$ matrix with coefficients in $GF(p)$ (i.e., coefficients taken modulo $p$). Let $B=A^k$, where $k$ is an integer not given to us. Given $p$, $A$, ...
2
votes
0answers
194 views
Bounding the spectral radius of a sub-stochastic matrix
Suppose that I have a "sub-stochastic" matrix, namely, for an $n\times n$ matrix $A$ with nonnegative entries such that
for any $i$, $\sum_j a_{ij}\leq 1$ and there exists some $i$ with $\sum_j ...
4
votes
0answers
87 views
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 ...
14
votes
1answer
314 views
Complexity of deciding whether a matrix is totally regular
A matrix is called totally regular if all its square submatrices have full rank. Such matrices were used to construct superconcentrators. What is the complexity of deciding whether a given matrix is ...
15
votes
2answers
1k views
How to compute powers of square matrices?
Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?
The next best thing in comparison to computing ...
10
votes
1answer
227 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 ...
2
votes
1answer
101 views
Finding mapping between two spatial representations of the same objects
I have two matrices $U$ and $V$. $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that ...
4
votes
1answer
260 views
On planarity in two related graphs
Let $A$ be an $(n\times n)$-matrix with entries from $\{0,1\}$ and $B$ its biadjacency matrix $B = \begin{pmatrix} 0 & A\\ A^t & 0 \end{pmatrix}$.
My simple question is: Is there a ...
12
votes
2answers
389 views
Complexity of Membership-Testing for finite abelian groups
Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...
5
votes
1answer
213 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 ...
9
votes
1answer
443 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 ...
9
votes
0answers
305 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 ...
12
votes
1answer
247 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 ...
3
votes
0answers
174 views
Convergence of HITS Algorithm in the absence of Normalization
Kleinberg's HITS Algorithm (Authoritative sources in a hyperlinked environment) requires the hub (/authority) vector to be normalized after each step of the iteration $x(k+1) = A.x(k)$, in order to ...
8
votes
3answers
284 views
Linear programming solution in one pass with ordered variables
I have a family of linear programming problems: maximise $c' x$ subject to $A x\le b$, $x\ge0$. The elements of $A$, $b$, and $c$ are nonnegative integers, $c$ strictly positive. ($x$ should also ...
1
vote
0answers
132 views
Row/column overlay problem for filling in a matrix
I was wondering if the following problem has been studied/has a name:
Given a matrix of numbers (may assume to be integers), find the smallest number of rules which define the matrix. Three kinds of ...
9
votes
1answer
216 views
What is the largest gap between rank and approximate rank?
We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication ...
2
votes
2answers
291 views
LU factorization of a 0-1 matrix
I have a rather naive question on LU factorization which probably should be easy to answer. Say I have a matrix with entries only from $\{0,1\}$. When can we expect to get an LU factorization of such ...
10
votes
1answer
384 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 ...
7
votes
0answers
455 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 ...
4
votes
1answer
120 views
On the properties of a family of submatrices
Let $n$ and $k \le n/2$ be positive integers, and consider a family $\mathcal{F}$ of $k\times k$ sub-matrices of an $n\times n$ matrix such that every two elements of $\mathcal{F}$ intersect. What ...
6
votes
1answer
228 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 ...
19
votes
2answers
471 views
Explicit balanced matrix
Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones?
Or probably it is ...
8
votes
1answer
777 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 ...
0
votes
0answers
308 views
Sort sorted matrix [duplicate]
Possible Duplicate:
What is a good special-case sorting algorithm?
Is there any linear-time sorting algorithm for sorting elements of a sorted matrix (a matrix with all rows and columns ...
0
votes
0answers
176 views
Matrix problem in C [closed]
In an mxn matrix having k objects, what are the number of ways that an object be placed in a matrix cell.(k<=n,m). By giving an example the more better illustrated, if the 1st object out of the "k" ...
31
votes
5answers
3k 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 ...
17
votes
1answer
619 views
Can we decide whether a permanent has a unique term?
Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne ...
14
votes
2answers
857 views
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:
...
14
votes
1answer
711 views
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 ...
16
votes
2answers
391 views
Lower bounds on Gaussian complexity
Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity ...
18
votes
1answer
364 views
Approximating the sign rank of a matrix
The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in ...
