People who code: we want your input. Take the Survey
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 ...


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$, ...


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.


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