Questions tagged [matrices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
24 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 ...
7
votes
0answers
122 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 ...
18
votes
0answers
360 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 ...
2
votes
1answer
90 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 ...
3
votes
0answers
136 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 ...
2
votes
0answers
65 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 ...
20
votes
4answers
1k 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: Positive topological ordering ...
-3
votes
1answer
51 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 $...
0
votes
1answer
267 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} ...
-4
votes
1answer
73 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: ...
19
votes
2answers
1k 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 \...
15
votes
2answers
4k 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
1answer
163 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 ...
1
vote
2answers
363 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?
41
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 ...
9
votes
1answer
526 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? ...
23
votes
2answers
661 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
39 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 ...
10
votes
2answers
367 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 ...
1
vote
0answers
90 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
104 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 ...
5
votes
2answers
2k views

Making an adjacency matrix positive semidefinite

I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can ...
4
votes
0answers
151 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.
4
votes
1answer
712 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 ...
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
236 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/...
8
votes
1answer
4k 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 ...
41
votes
6answers
14k 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 ...
2
votes
0answers
64 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
232 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
128 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
84 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
171 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
421 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
533 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 ...
3
votes
1answer
171 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?
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
248 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
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
256 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

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$ ...
24
votes
1answer
3k 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 ...
2
votes
1answer
97 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
196 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\...
6
votes
1answer
218 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 ...
2
votes
0answers
112 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 ...
1
vote
0answers
146 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$?
1
vote
1answer
136 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 ...
2
votes
1answer
400 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 ...