29
There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for it comes from Coppersmith's paper "Rapid multiplication of rectangular matrices", but the explanation for why it leads to $N^2 \operatorname{polylog}\left(N\...
22
No such matrix exists.
The Desnanot-Jacobi identity says that for $i \neq j$,
$$
\det M_{ij}^{ij} \det M = \det M_i^i \det M_j^j -\det M_i^j \det M_j^i
$$
so using this, we get
$$
\det M_{12}^{12} \det M = \det M_{1}^{1} \det M_{2}^{2} - \det M_{1}^{2} \det M_{2}^{1}
$$
But your requirements force the left-hand-side to be 0 (mod 2) and the right-hand-...
20
As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix ...
17
Expanding my comment:
Computing the permanent of a matrix is #P-hard (Valiant 1979) even if the matrix entries are all either 0 or 1.
We can interpret a matrix $M \in \{0,1\}^{n \times n}$ as a bipartite graph $G$ with left vertices $[n]$ and right vertices $[n]$, where the edge $(i,j)$ is present if and only if $M_{i,j}=1$. A perfect matching is a subset ...
16
There will generally not exist a set of $n$ linearly independent vectors $x$ such that $Ax = x$; this can only happen for $A$ being the identity matrix. On the other extreme, there may be no such vectors at all. For example, the matrix
$$
A = \left(\begin{array}{cc} 0 & 1\\ 1 & 1 \end{array}\right)
$$
has full rank, but there are no nonzero vectors ...
16
If you allow the repetition of matrices, i.e. there exists $ 1 \leq i < j \leq n $ s.t. $ A_i =A_j $, then your problem is actually undecidable.
Let $ EMPTY_{PFA} $ be the emptiness problem for probabilistic finite automaton (PFA).
A PFA is a 4 tuple: $ P=(\Sigma,\{A_{\sigma \in \Sigma}\},x,y) $, where $\Sigma = \{\sigma_1,\ldots,\sigma_k\}$ is the ...
15
The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order.
It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you ...
15
De Groote (On Varieties of Optimal Algorithms for the Computation of Bilinear Mappings. II. Optimal Algorithms for 2x2-Matrix Multiplication. Theor. Comput. Sci. 7: 127-148, 1978) proves that there is only one algorithm to multiply $2 \times 2$-matrices with 7 multiplications up to equivalence. This might be a unique feature of $2 \times 2$-matrix ...
14
The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers
There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.
13
The paper Vandermonde Matrices, NP-Completeness, and Transversal Subspaces [ps] by Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran may be relevant to your question (though it does not answer it).
They prove the $\mathsf{NP}$-completeness of the following problem: Given an $n\times m$ matrix over $\mathbb Z$ ($n\le m$), decide whether ...
12
Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that
there exists an efficiently computable matrix $M$ with sign pattern $S$ such that $\mathrm{rank}\ M = O(n^{1-1/d})$;
the sign rank of $S$ is at least $d$.
So the algorithm computes $M$ and outputs ...
12
The exponent of computing a basis of the kernel is the same
as the exponent of matrix multiplication, see the
book Algebraic Complexity Theory by Bürgisser, Clausen & Shokrollahi.
So it can be done in time $O(n^{2.38})$.
12
For matrices of sizes $k = 2,3$ the Matrix Powering Positivity Problem is in $\mathsf{P}$ (cf. this paper to appear in STACS 2015)
12
It is not known if there is an $\varepsilon > 0$, $c > 2$, and $k > c$ such that $(c,k)$ hyperclique is in $n^{k-\varepsilon}$ time. Note that the case of $k \leq c$ is trivial. For years I have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving $k$-Sat. (Several open problem sessions at ...
12
Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$
Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn ...
11
Matrices A and B whose elements are in a field F are similar (in F) if and only if they have the same Frobenius normal form. According to a quick search, it seems that the Frobenius normal form of an n×n matrix can be computed with O(n3) field operations [Sto98], and that this can be improved to something comparable to the complexity of matrix ...
11
There is some sort of explanation in the book Algebraic Complexity Theory by Bürgisser, Clausen and Shokrollahi (p. 11-12). The idea is to start with two bases $A_0,A_1,A_2,A_3$ and $B_0,B_1,B_2,B_3$ of the space of $2\times 2$ real matrices which satisfy the following property: $A_iB_j \in \{0,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3\}$. Furthermore, $A_0 = B_0$. To ...
11
$\mathcal{G}_B$ is the bipartite double cover of $\mathcal{G}_A$. So it has twice as many vertices and edges, and if $\mathcal{G}_A$ has an embedding with $x$ even faces and $y$ odd faces then $\mathcal{G}_B$ has an embedding (possibly on a nonplanar surface) with $2x+y$ faces, formed by making two copies of each even face and replacing each odd face by its ...
11
Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of Coppersmith-Winograd) - would "simply" produce a family of algorithms $A_\epsilon$ running in time $O(n^{2+\epsilon})$. So to have a single algorithm which ran in $O(n^2 ...
10
Verifying whether $b \in \langle h_1, \ldots, h_n\rangle$ (where $h_i$ are vectors according to the OP's comments) is equivalent to verifying whether there is a solution to this system:
$$
\begin{pmatrix}
h_{1}(1) & \cdots & h_{n}(1) & d_1^{e_1} & 0 & \cdots & 0 \\\\
\vdots & \ddots & \vdots & \vdots & \vdots ...
10
The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.
Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.
The type of reductions you'd need ...
10
Josh Alman showed some cool lower bound results of MM, which won CCC 2019 best student paper award!
http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf
9
First I'll give some background and define approximate rank. A good reference is the recent survey by Lee and Schraibman Lower Bounds on Communication Complexity.
Definition: Let $A$ be a sign matrix. The approximate rank of $A$ with approximation factor $\alpha$, denoted $rank^\alpha(A)$, is
$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \...
9
According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known.
According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ both large) to
$$\exp (z_{\mathrm{sq}}mn)$$
where
$$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$
but I'm not sure ...
9
This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history).
A linear circuit is an algebraic circuit whose only gates are two-input linear combination gates. Every linear transformation (matrix) can be computed by a linear circuit of quadratic size, and the question is when can ...
9
Here's just a couple of observations I couldn't fit in a comment:
0) Added because the first answer was deleted: there is an interpretation of $H_n$, namely, indexing the rows and columns by $\{0,1\}^n$, the entry corresponding to $(x,y)$ is $1$ if the Hadamard product $x\odot y=(x_1y_1,\ldots,x_n y_n)$ has even parity, and $-1$ if it has odd parity.
1) In ...
9
An observation too long for a comment (and which also fits well with Jason Gaitonde's observation-too-long-for-comment):
As hinted at in the OQ, both of these can in fact be realized by a very simple kind of recursive construction. Namely, we specify $B_0 \in \{(0), (\pm 1)\}$ (a $1 \times 1$ matrix), and then a single recursive formula
$$
B_n = \left(\...
8
The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}_{p,r}$ is known to be difficult". (Here $\mathcal{P}_{p,r}$ is the problem of computing the norm $\|A\|_{p,r} = \sup_{\|x\|_p=1} \|Ax\|_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}_{\infty,1},\mathcal{P}_{\infty,2},\...
8
You can do this in uniform NC, see:
G. Villard. Fast parallel algorithms for matrix reduction to canonical forms. AAECC 8:511-537, 1997. http://link.springer.com/article/10.1007%2Fs002000050089
8
No.
Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. Computing $AB^T$ from $A$, $B$ and $AB$ means computing $XY^T$ from $X$ and $Y$, since $AB = 0$
Only top voted, non community-wiki answers of a minimum length are eligible
