25

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random vectors. This method reduces the time complexity from $O(n^{2.3729}$) (regular matrix multiplication) to $O(n^2)$ with high probability. In your case, the matrices $...


8

tl;dr: You can make a rough probabilistic judgement in $O(1)$ time Let's assume you are willing to settle on a test which differentiates "good" matrices $A,B$ from "pretty bad" $A,B$, in the following sense: If $A \times B = I$, the test will accept with high probability. If $A \times B$ is far* from $I$ , the test will reject with high ...


6

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem: While the proof of theorem (1.1.13) is somewhat involved, the ...


4

For an $n \times m$ matrix $M$, define the potential function $$ \Phi(M) = \sum_{i=1}^n \sum_{j=1}^m 2^{n-1-i} 2^{m-1-j} M(i,j). $$ If we write it as $$ \Phi(M) = \sum_{i=1}^n 2^{n-1-i} \sum_{j=1}^m 2^{m-1-j} M(i,j) $$ then it immediately follows that reordering rows either fixes $M$, or strictly increases $\Phi$. Similarly, reordering columns either fixes $...


3

Since your matrices are small $(50 \times 50)$, you can probably just compute $M^t$ through repeated exponentiation where the exponents are powers of $2$. Write $t$ in binary so that $t = 2^{k_1} + 2^{k_2} + \dots + 2^{k_\ell}$. Then $M^t = \prod_{i=1}^\ell M^{2^{k_i}}$. Moreover, for $k_i \ge 1$ you have $M^{2^{k_i}} = \left( M^{2^{k_i - 1}} \right)^2$, ...


3

I would consider a sentence such as this to be unambiguous: We flattened the $h \times w \times 3$ input data down to a two-dimensional $hw \times 3$ shape. I don't believe a reference explaining this would be necessary.


3

The problem is NP-hard; it is at least as hard as the biclique problem. If you can solve the problem for a single shaped box, you can solve for all boxes by just iterating over all the boxes. So your problem reduces to: Given a matrix $M$ and integers $h', w'$, find a $h'\times w'$ submatrix of $M$ that is all ones, or report that none exists. This ...


2

This was proved NP-complete in "Optimal Packing and Covering in the Plane are NP-complete" (Fowler, Paterson and Tanimoto, Information Processing Letters 1981). I found a freely available version of the paper here. They give a neat reduction from 3SAT -- I'll summarise this below, but the paper is short and easy-to-read with several diagrams, and I ...


2

We get the recurrence by considering all possible ways of breaking up $A_i \times \cdots \times A_j$. Specifically, we consider $(A_i \times \cdots \times A_k) \times (A_{k+1} \times \cdots \times A_j)$ for all relevant values of $k$, which are $i,\ldots,j-1$.


2

Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log_27}$. Now suppose that we are given two $n\times n$ matrices. We pad them to $N \times N$ matrices, where $N = 2^{\lceil \log_2 n \rceil} < 2n$. We can extract ...


2

I tried it on square grayscale images myself (just hoping they would be invertible, which was always the case (not much luck involved here, since invertible matrices lie dense)). I added a few examples so you can judge the inverses yourself. Their precise look of course depends on the particular normalization (I used cv2.normalize and also normalized ...


2

We are looking for a curve $$ P(u) = a_3 u^3 + a_2 u^2 + a_1 u + a_0 $$ which satisfies the following properties: $P(0) = P_i$. $P(1) = P_{i+1}$. $P'(0) = P'_i$. $P'(1) = P'_{i+1}$. In terms of the coefficients $a_0,a_1,a_2,a_3$, these are: $a_0 = P_i$. $a_3 + a_2 + a_1 + a_0 = P_{i+1}$. $a_1 = P'_i$. $3a_3 + 2a_2 + a_1 = P'_{i+1}$. In matrix form, this ...


1

Ben Rossman showed that any unbounded fan-in depth $d$ circuit for your problem has size at least $n^{\Omega(m^{1/2d})}$. Conversely, a simple recursive construction gives an unbounded fan-in depth $d$ formula of size $n^{O(m^{1/d})}$.


1

I suggest using xtensor. You can compute the 4000-th matrix power of M as xt::linalg::matrix_power(M, 4000). Obviously you should be aware that powering in any language can incur in numerical issues. Even if your matrix is 1 x 1, M^4000 could be enormous, larger than what you could store as a floating point value.


1

If $A$ is an $n \times m$ dense matrix then $AA^T$ is an $n\times n$ matrices given by $$ (AA^T)_{ij} = \sum_{k=1}^m A_{ik} A_{jk}. $$ This gives a $\Theta(n^2m)$ algorithm for computing $AA^T$. If $n \geq m$ then faster algorithms exist, but they are not used in practice (at least in most situations). If $A$ is sparse, that is, stored as a list of non-zero ...


1

This is a known problem: https://binarysearch.com/problems/Minimum-Light-Radius Key Idea: Binary search for the diameter, then use that to find the radius.


1

Let us recall that $$ F_n = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}. $$ We compute the $n$-th Fibonacci number using the method of repeated squaring, applied to the $2\times 2$ matrix. The matrices encountered during this process are all of the form $$ A_m = \begin{...


1

It's unnecessary to perform an LU factorization each time. Instead, you can compute a projection matrix $P$ from your dense matrix. Then, for any vector $x$ in your set, just check if $Px = x$. In particular, suppose your original dense matrix $A^T$ has all of its rows independent (if it doesn't just delete rows until it does) and you wanted to know if ...


1

Based on the, apparently famous paper on the field, Ryser 56, and the thesis recommended by @orlp, the test to know if a row and column sum vectors forms a match, e.g., a matrix $M_{h,w}$ exists having these row and column sum vectors, is the following one: Let $R_h$ be a vector of $h$ elements sorted in a non-increasing order ($r_1\geq r_2\geq\ldots\geq ...


1

In real problems when the size is large ($n>100000$) the best approach is the numerical solution of the system by an iterative method like GMRES, CG, BiCG, etc. All those algorithms depends strongly on matrix-vector products, so the complexity is as much as $O(n^2)$ which performs better than a direct solution by a LU decomposition with complexity of $O(n^...


Only top voted, non community-wiki answers of a minimum length are eligible