The tag has no usage guidance.

learn more… | top users | synonyms (1)

-3
votes
0answers
44 views

Show that this binary matrix problem is in P [closed]

Given the following problem: MBMP: Input: a binary Matrix $M∈ \{0, 1\}^{(n×m)}$ where every pair of two rows are pairwise unequal but only differ in at most 2 columns and one of the rows only ...
3
votes
1answer
75 views

Low-depth arithmetic complexity of the product of $k$ matrices

Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices? Trivial upper bounds (up to small factors) are: if $k=2$, then there are $\...
3
votes
3answers
116 views

Canonisation of boolean matrices under row and column permutations

Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows: $A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\...
3
votes
0answers
80 views

On FFT and trigonometric matrix eigenvalues

Let $N=2^n$ for a natural number $n$ and $B$ be the $N\times N$ square matrix of $0$'s and $1$'s $$ B=\begin{pmatrix} 0 & 1 & 0 & \ldots & 0 \\ 1 & 0 & 1 & \ldots ...
6
votes
1answer
186 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 ...
0
votes
0answers
88 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$?
3
votes
1answer
185 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 ...
0
votes
1answer
77 views

Low rank approximation of matrix under $l_2$ norm

Theorem 14 of this paper by Tam´as Sarl´os gives a relative error rank-$k$ approximation of a given matrix $A$ under the frobenius norm. I am looking for reference of a similar result (relative error ...
12
votes
4answers
430 views

Finding the sparsest solution to a system of linear equations

How hard is it to find the sparsest solution to a system of linear equations? More formally, consider the following decision problem: Instance: A system of linear equations with integer coefficients ...
2
votes
2answers
200 views

Submatrix of small rank

Let $G=(V,E)$ be a graph with adjacency matrix $M=(m_{ij};i,j \in V )$ over $\mathbb{F}_2$ and $k \in \mathbb{Z^+}$. How can we find in polynomial time a subset $A \subseteq V$ such that The rank ...
14
votes
0answers
463 views

Does solving matrix multiplication in quadratic time imply that SETH is false?

I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time. In other words, ...
5
votes
2answers
389 views

Matrix permanent is 0

Valiant's theorem says that computing the permanent of an $n\times n$ matrix is #P-hard. Is the problem of determining if a permanent is 0 any easier? This arises in the context of sequence A006063 in ...
-1
votes
1answer
139 views

Graph isomorphism problem with invertible adjacency matrices

This question is supplementary to the question asked here. One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows. Given a ...
9
votes
2answers
201 views

Matrix vector multiplication algorithm using minimal number of additions

Consider the following problem: Given a matrix $M$ we want to optimize the number of additions in the multiplication algorithm for computing $v \mapsto Mv$. I find this problem interesting ...
6
votes
1answer
191 views

Arithmetic complexity of matrix powering

Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables. We know that size of smallest formula that computes $\mathsf{Tr}(M^d)$ where $d\in\Bbb N$ could be ...
3
votes
1answer
94 views

“How much diagonal” a matrix is

I have a (biological) computational system that outputs squared matrices. These matrices will sometimes have a tendency to be diagonal-like, with higher values at and around the diagonal. I would ...
5
votes
1answer
197 views

Complexity of k-clique for hypergraphs

Classic Problem: Let a number $k$ be given. The $k$-clique problem is as follows. Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent? ...
2
votes
0answers
90 views

Complexity of a particular determinant

Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant ...
2
votes
0answers
37 views

Products of PSD matrices that equal an orthogonal matrix

You have k symmetric real n-by-n matrices A_1...A_k, each bounded by some parameter eps < 1/2 in spectral norm. You know that the product (Id+A_1)(Id+A_2)...(Id+A_k) equals an orthogonal matrix Y. ...
9
votes
2answers
164 views

Exact formula for the number of spanning trees of a rectangle

This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for ...
2
votes
1answer
107 views

Minimal set of Hyperrectangles covering an n-dimensional binary matrix with row permutations

My input is a n-dimensional binary matrix. My goal is to find the set of Hyperrectangles that covers every '1' at least once and covers not a single '0', which has minimal cardinality (the least ...
1
vote
0answers
70 views

Matrix of ranking

In any graph of n nodes in any dimension, define matrix $M_r$ of ranking as $\forall r_{ij}\in M_r$, $r_{ij}$ is the ranking of j to i. That is, j is the $r_{ij}$th nearest node to i. Therefore, any ...
-1
votes
1answer
53 views

Find non-intersecting submatrices

I have a rectangular boolean matrix and I'd like to have an efficient algorithm to find non-intersecting submatrices. I'll to demonstrate that in the example below. The ideal case is when all ...
3
votes
1answer
145 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
vote
0answers
56 views

Low rank Log rank conjecture

What is known about log rank conjecture in special situations of $O(\log N)$ rank $0/1$ matrix of size $N\times N$? Is there at least a conditional result showing better than $O(\sqrt{\log N})$ bound?
2
votes
0answers
53 views

Parameterized Complexity of Minimum Type Selection

Consider the following problem that I call »Minimum Type Selection«: Input: $k$ sets of bit vectors, each of length $n$ and a number $l$. Question: Is it possible to pick exactly one bit vector from ...
0
votes
0answers
45 views

Is there a diagonal matrix D such that DMD is SDD, where M is SPD matrix

Let $M$ be symmetric and positive definite matrix (SPD). It is known [1] that if $M$ is SPD and in addition satisfies $M_{ij}\leq 0$, for $i\neq j$ (called M-matrix) then there is a positive ...
3
votes
0answers
44 views

Reference for Nuclear Norm Relaxations

I have seen a bunch of results concerning Matrix Completion, PCA, Compressed Sensing where a common theme has been to relax the Rank constraint/objective by replacing it with Nuclear Norm. I was ...
1
vote
0answers
37 views

Eigenvalues of Random Regular Bipartite Graphs

I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...
5
votes
0answers
101 views

Tools to bound the singular values of a finite sum of random matrices from below?

Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
1
vote
0answers
44 views

On Gaussian Weight matrix and rank

Suppose one has a set of $n$ points in $\mathbb{R}^d$, where the points are represented as $p_1$ through to $p_n$. Define the weight matrix $W$ as follows: let $W_{i,j}$ be $e^{-||p_i - p_j ||^2}$, ...
0
votes
1answer
92 views

What is known about matrix multiplication, and matrix circuits?

So I'm wondering, first off, where I can read up to get a feel for state-of-the-art matrix multiplication concepts. I'll try to be more specific: I'm wondering if there has been research on circuits ...
4
votes
1answer
87 views

Proving PSD-ness of matrices

Diagonally dominant matrices are known to be positive semidefinite (PSD). What are some other families of (symmetric) matrices which are known to be PSD? Given an arbitrary matrix A, the ...
22
votes
0answers
583 views

Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

The following question arose as a side product of some work I have been part of recently. An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a ...
6
votes
0answers
309 views

Best algorithm for inversion of symmetric positive-definite matrices

As I know, the time complexity for usual inversion algorithm of general matrix is $O(n^3)$. In recent years, there is a improvement from $O(n^3)$ to $O(n^{2.8....})$. However, does there exists a ...
4
votes
1answer
309 views

Reducing the bandwidth of non-symmetric matrix

Is there an efficient algorithm to reduce the bandwidth of a directed graph's adjacency matrix? Something like the reverse Cuthill-McKee, but for non-symmetric matrices.
2
votes
0answers
113 views

Computing dual of the spectral norm of tensor of order 3

It is shown in http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf that computing the spectral norm (see Definition 6.6) of a $3^{rd}$ order tensor $T \in \mathbb{R}^{d_1 \times d_2 \times d_3}$ is NP-...
3
votes
1answer
280 views

A matrix rank problem over finite fields: Is that a known problem?

The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated. Let $A \odot B$ denote elementwise multiplication of ...
3
votes
0answers
167 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
77 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 ...
3
votes
1answer
202 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
211 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
42 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
91 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
101 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
120 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, ...
4
votes
1answer
124 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 ...
5
votes
1answer
201 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 related ...
4
votes
1answer
246 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
458 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 ...