Questions tagged [matrices]
The matrices tag has no usage guidance.
142
questions
3
votes
0
answers
131
views
+50
Deciding if all matrix multiplication entries have at least two witnesses
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N×N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C=AB$ (not boolean matrix multiplication but the ...
- 1,015
0
votes
0
answers
91
views
How far easier is Boolean matrix multiplication, compared to matrix multiplication?
It is obvious that boolean matrix multiplication can be solved in $O(n^\omega)$, as a simple variant of regular matrix multiplication. I saw a recent paper solving boolean matrix multiplication in $O(...
2
votes
0
answers
44
views
Sorting multiple columns of a matrix
Let $A \in \mathbb{R}^{n \times k}$ be a matrix where each column contains all of the numbers from $\{1,\dots,n\}$ in some arbitrary order. For example, if $n=3, k=2$, we could have
$$ A =
\begin{...
- 179
0
votes
0
answers
101
views
What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?
The Question:
I'm trying to understand the type of problems that Quantum Computers are/will be good at solving and if there is a special class to categorizes these types of problems (e.g. Do we ...
- 109
1
vote
0
answers
66
views
Smallest nonzero eigenvalue of a sum of +1/-1 rank-one matrices?
Suppose we have a $k\times k$ matrix $A = \sum_{i=1}^{n} a_i a_i^T$ where $n \leq \mathrm{poly}(k)$ and each $a_i\in\{-1,1\}^{k}$. It is easy to prove that the largest eigenvalue of $A$ is at most $\...
- 31
1
vote
1
answer
157
views
Finding output with unique witness in matrix multiplication
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication ...
- 1,015
2
votes
0
answers
69
views
Obtaining a lower bound of a matrix norm
I was wondering (on a setting where $\vec X_i \sim \mathcal{N}(\vec\mu, \mathbb{I})$ are $n$ random $d$-dimensional multivariate normal vectors with unknown mean $\vec\mu$) how I could obtain a lower ...
- 21
2
votes
1
answer
116
views
Solver for uniform matroid isomorphism
I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as $k \times n$ matrix over a finite field $\mathbb{F}_p$ (where $p$ is large prime), ...
- 1,422
3
votes
1
answer
60
views
Problem conditions to use Laplacian solvers
I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense.
Suppose that we want to solve Ax=b, ...
- 133
1
vote
0
answers
37
views
Remove cycles from a stochastic comparison matrix, while doing the least amount of editing
Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
- 217
7
votes
0
answers
158
views
Reference for computing the rank of a matrix in polynomial time
In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
- 171
18
votes
0
answers
447
views
In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?
Decision Problem
Input: An $m$ by $n$ Boolean matrix $M$.
Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
- 4,900
2
votes
1
answer
133
views
Compiling einstein sums optimally
Einstein summation is a convenient way to express tensor operations which has found its way in tensor libraries like numpy, torch, tensorflow, etc.
Its flexibility lets us represent the product of ...
- 225
3
votes
0
answers
142
views
Dynamic matrix-matrix multiplication
Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1". The result of each ...
- 321
2
votes
0
answers
78
views
Is there a fast algorithm for computing the Schmidt decomposition
I have a huge covariance matrix, 𝑀, with the dimension, e.g., $10^8 \times 10^8$. Luckily enough, the number of nonzero eigenpairs, $n$, is very small, i.e., $n<5$. From the computational ...
- 21
-3
votes
1
answer
85
views
Finding a non-negative solution to an integer system of linear equations
Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
- 215
0
votes
1
answer
965
views
Time complexity for multiplying two lower triangular matrices
I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
...
- 141
-4
votes
1
answer
407
views
Distinguish Graph from Tree using Adjacency Matrix
Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle).
For example, given the adjacency matrix:
...
- 1
10
votes
1
answer
228
views
The complexity of the permanent of low rank matrices
I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank ...
- 103
41
votes
3
answers
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 ...
- 511
23
votes
2
answers
712
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{...
- 4,341
2
votes
0
answers
40
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 ...
- 189
1
vote
0
answers
95
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 $$...
- 19
-4
votes
1
answer
209
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 ...
- 93
4
votes
0
answers
158
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.
- 141
1
vote
0
answers
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 ...
1
vote
1
answer
279
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/...
- 203
2
votes
0
answers
66
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?
- 189
6
votes
1
answer
252
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-...
- 31.6k
0
votes
1
answer
34
views
Decomposing outer product or general rank factorization over $\Bbb F_q$
Given matrix $M\in\Bbb F_q^{n\times n}$ with the promise that there are two matrices $A\in\Bbb F_q^{n\times 1}$ and $B\in\Bbb F_q^{1\times n}$ such that $AB=M$ is there a deterministic $O((n\log q)^c)$...
- 12.5k
1
vote
0
answers
134
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 ...
- 193
0
votes
0
answers
98
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}$ ...
- 12.5k
2
votes
1
answer
194
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 ...
- 12.5k
3
votes
0
answers
662
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 ...
- 131
26
votes
0
answers
607
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 ...
- 746
6
votes
1
answer
136
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 ...
- 163
7
votes
1
answer
262
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 ...
- 233
5
votes
0
answers
206
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 ...
- 12.5k
1
vote
1
answer
94
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$ ...
- 771
2
votes
1
answer
265
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 ...
- 12.5k
1
vote
1
answer
98
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 ...
- 11
2
votes
1
answer
108
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 $\...
- 829
3
votes
3
answers
213
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\...
- 33
2
votes
0
answers
145
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 ...
- 71
6
votes
1
answer
220
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 ...
- 73
1
vote
0
answers
166
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$?
- 73
2
votes
1
answer
475
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 ...
- 717
1
vote
1
answer
142
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 ...
- 629
13
votes
4
answers
1k
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 ...
- 4,900
3
votes
2
answers
287
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 ...
- 1,984