# Questions tagged [matrices]

The tag has no usage guidance.

136 questions
Filter by
Sorted by
Tagged with
93 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 ...
62 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 ...
110 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), ...
3k views

### Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix . For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
53 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, ...
16k 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 ...
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 ...
143 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 ...
411 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 ...
109 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 ...
139 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 ...
72 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 ...
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 ...
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 $... 1answer 668 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} ... 1answer 199 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: ... 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 \... 2answers 5k 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 ... 1answer 190 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 ... 2answers 372 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? 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 ... 1answer 735 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? ... 2answers 685 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{... 0answers 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 ... 2answers 433 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 ... 0answers 93 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$$... 1answer 150 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 ... 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 ... 0answers 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. 1answer 778 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 ... 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 ... 1answer 259 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/... 1answer 5k 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 ... 0answers 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? 1answer 236 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-... 0answers 132 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 ... 0answers 89 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}$... 1answer 183 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 ... 0answers 547 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 ... 0answers 559 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 ... 1answer 173 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? 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 ... 1answer 254 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 ... 0answers 203 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 ... 1answer 96 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 ... 1answer 257 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 ... 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$... 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 ... 1answer 102 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$\...
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\...