People who code: we want your input. Take the Survey

# Tag Info

## Hot answers tagged matrices

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