Questions tagged [matrices]
The matrices tag has no usage guidance.
122
questions
40
votes
3answers
5k views
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are ...
23
votes
2answers
624 views
Question about two matrices: Hadamard v. “the magical one” in the proof of the sensitivity conjecture
The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows:
$$A_1 = \begin{...
2
votes
0answers
38 views
Minimize The Number of Connected Components in Hit-map of A Boolean Matrix
Suppose there is a matrix with the value of 0 and 1. The hit-map of the matrix (0 is blue and 1 is red) create some connected component (see the following figure as an instance):
Is there any ...
1
vote
0answers
85 views
Complexity of low-rank matrix factorizations with rows in a simplex and outliers
Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies
$$ \sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0 $$...
-4
votes
1answer
91 views
Ordering of sub problems in dynamic programming
1) Can every dynamic programming question be solved using 3 different orderings or can there be more than 3 or less than 3 ( like unique ordering )?
My understanding is that a) it might have a unique ...
4
votes
0answers
148 views
research problem for undergraduate majoring in Computer Science and Mathematics
I am wondering if somebody can suggest a small research problem for undergraduate majoring in Computer Science and Mathematics. Would love to work with random matrices or wavelets.
1
vote
0answers
59 views
Finding a Minimal k-Subgraph
Given a complete, positively weighted, bidirectional graph with $n$ nodes without self-loops. Hence the corresponding adjacency matrix $A$ is positive, symmetric, and has zero main diagonal. I am ...
0
votes
1answer
207 views
Open/unsolved problems in (computational) random matrix theory / matrix completion?
I was wondering what some open problems are in random matrix theory (especially those of interest to TCS people/so mainly non-asymptotic things, I imagine). Also, and relatedly, what are remaining/...
2
votes
0answers
60 views
Efficient Online Algorithms for Matrix rank
Suppose, we have a matrix with known rank. Then, in each step one element of this matrix will be changed. Is there any efficient online algorithm to find rank of each matrix after each element update?
6
votes
1answer
223 views
Algebraic account of Gaussian elimination?
For fun, I've been looking at the interpretation of linear logic in terms of finite-dimensional vector spaces, and ran into an interesting
question about the interpretation of double-negation-...
1
vote
0answers
124 views
Connection between diamond norm and output purity norm
Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register ...
0
votes
0answers
83 views
On permanent mod $3^t$ computation
By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent.
We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ ...
2
votes
1answer
159 views
Complexity of $\{0,\pm1\}$ determinant in sparse cases?
If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?
Assume that the matrix ...
2
votes
0answers
262 views
Is there any algorithm to find just the largest eigenvalue with subquadratic time complexity?
SVD or PCA can be used find the largest eigenvalue, but at a cost of $O(n^3)$ complexity. Lanczos algorithm runs much faster on a sparse matrix with complexity $O(dn^2)$ where $d$ is the average ...
26
votes
0answers
496 views
Rank mod 6 vs rank over the reals
Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}_2$ and over $\mathbb{F}_3$. Does this imply that $A$ has low rank over the reals? This seems ...
6
votes
1answer
132 views
What's the complexity of factoring over a set of generators (say in $GL_2$)?
In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know ...
7
votes
1answer
242 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 ...
5
votes
0answers
202 views
On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input.
Is ...
1
vote
1answer
93 views
Properties of convex polytope of 0-1 matrices
Problem setting
Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$.
Consider a $k\times k$ matrix $M$ ...
2
votes
1answer
251 views
Complexity involving connected components of 0/1 matrix
Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you ...
1
vote
1answer
94 views
reference request- property of subset of rows in a matrix
I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M ...
2
votes
1answer
94 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
179 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\...
2
votes
0answers
101 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
216 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 ...
1
vote
0answers
136 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$?
2
votes
1answer
385 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 ...
1
vote
1answer
133 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 ...
13
votes
4answers
867 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
249 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 of ...
14
votes
0answers
582 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
1k 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 ...
0
votes
1answer
181 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 ...
10
votes
2answers
248 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
213 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
276 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 ...
9
votes
1answer
434 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
120 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
42 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.
...
10
votes
2answers
307 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 ...
3
votes
1answer
125 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
71 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
72 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
275 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 ...
3
votes
1answer
166 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
56 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
98 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
46 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
94 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
117 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 ...
