The tag has no wiki summary.

learn more… | top users | synonyms (1)

3
votes
0answers
113 views

An interesting construction of a Tits building?

The notion of Tits building was introduced by Jacques Tits to study certain questions in group theory. The wikipedia entry gives a way to construct a Tits building from a vector space, but I would be ...
2
votes
0answers
56 views

Convergence of iterated stochastic matrices

(This question has been unsuccessfully asked on mathoverflow: http://mathoverflow.net/questions/161728/convergence-of-iterated-stochastic-matrices) It is well-known that for a stochastic aperiodic ...
2
votes
1answer
102 views

Parallel (NC) replacements for Gaussian elimination?

Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine its rank, and a basis for its null-space. These can be computed ...
2
votes
1answer
144 views

Extensions of Matrix-Tree Theorem

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) ...
3
votes
0answers
31 views

Best complexity bound for parallel matrix-vector product?

I'm looking for the best known complexity (and a bound for the number of processors invoved) to do the calculation of a $(n,n)$ matrix-vector product. Thank you
4
votes
0answers
71 views

Constructing a small (n,k)-Covering Matrices family

Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$. We call ${\cal A}$ a (n,k)-covering, if for every subset of columns $I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in ...
3
votes
1answer
89 views

compleixty of rational checking of eigenvalues

Given a matrix $A$ with rational entries, how to check whether all the eigenvalues of $A$ are rational? What's the complexity of this problem? It seems that this can be done in polynomial time, but ...
2
votes
0answers
86 views

How is the complexity of PCA $O(\min(p^3,n^3))$?

I've been reading a paper on Sparse PCA, which is: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf And it states that, if you have $n$ data points, each represented with $p$ features, ...
3
votes
1answer
87 views

Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?

Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient ...
4
votes
1answer
160 views

any connection between binary/integer multiplication and matrix multiplication?

is there a connection between the inherent complexity of binary/integer multiplication algorithms and matrix multiplication algorithms? if so what is a ref that outlines/discusses it? some ...
4
votes
1answer
193 views

What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties?

More specifically, I'm looking at the problem of applying an algorithm for computing the permanent of a sparse matrix of binary entries (0s and 1s) to a matrix that has entries of positive and ...
13
votes
1answer
423 views

What's the complexity to check whether a matrix is Diagonalizable?

Given an $n\times n$ matrix $A$ with rational entries. What's the complexity to check $A$ is diagonalizable? I suspect that this can be done in P, but I do not know any reference. However, a more ...
7
votes
2answers
295 views

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$ ...
1
vote
0answers
94 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 ...
5
votes
0answers
118 views

Squares of random binary matrices

Are there results/techniques pertaining to the analysis of squares of random matrices ? More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with ...
2
votes
0answers
79 views

normalized tensor rank

Is there such a thing as a "normalized tensor rank" for non-square tensors (i.e. a tensor with different sizes along each mode)? For example: If a 3rd order tensor (dimensions = 60 x 120 x 30) has ...
11
votes
0answers
144 views

the largest element of a matrix product

Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to ...
5
votes
1answer
140 views

The computational complexity of spectral norm of a matrix

How hard is computing the spectral norm of a matrix? This paper says, ... it suffices to say that, except for few particular cases, the Matrix Norm problem is NP-hard. I expected that the ...
7
votes
0answers
214 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, ...
8
votes
0answers
167 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
55 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 ...
0
votes
2answers
199 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?
16
votes
2answers
288 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
321 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
166 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
186 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 ...
4
votes
2answers
224 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
62 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$ ...
5
votes
0answers
334 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 ...
10
votes
1answer
313 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.
23
votes
0answers
570 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 ...
10
votes
1answer
161 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
217 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$, ...
4
votes
0answers
262 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
102 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 ...
18
votes
3answers
470 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 ...
16
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 ...
11
votes
1answer
261 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
104 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
272 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
440 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 ...
7
votes
1answer
265 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 ...
10
votes
1answer
466 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 ...
11
votes
0answers
411 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 ...
13
votes
1answer
270 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 ...
4
votes
0answers
254 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
314 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
137 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 ...
10
votes
1answer
233 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
323 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 ...