How can I quickly judge whether matrix A is the inverse matrix of B?
This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution may be related to randomized algorithms.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Well it depends on the running time requirements. The simplest way is to try and multiply them, and see if you get the identity matrix, but probably they want something more sophisticated $\endgroup$– nir shaharCommented May 27, 2021 at 9:54
-
$\begingroup$ @nirshahar yeah I think so too. If it allowed to output wrong answer sometimes, is there any more quick algorithm? $\endgroup$– t24akeruCommented May 27, 2021 at 10:03
-
$\begingroup$ Perhaps one idea is to establish (tight) lower and upper bounds on the norm of a general matrix $\boldsymbol{B}$ based on the norm of $\boldsymbol{A}$ and then check if it falls in the range. Frobenius norm may be a good candidate, amongst others. $\endgroup$– user137086Commented May 28, 2021 at 11:34
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
7
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 $A$ and $B$ would be the matrices you are given, and the matrix $C$ would be the identity matrix.
-
11$\begingroup$ It's almost a bit pretentious to call this an algorithm. It's basically just throwing random inputs at a function and checking the results! $\endgroup$ Commented May 27, 2021 at 18:00
-
6$\begingroup$ @leftaroundabout Well, that's an algorithm anyhow. Only it will never give the answer "yes" but rather "hmm, I'll bet you a dollar it is true". $\endgroup$ Commented May 28, 2021 at 0:24
-
10$\begingroup$ @leftaroundabout How is that a quabble? As far as I know, being simple and obvious is a positive for algorithms. $\endgroup$– CeciliaCommented May 28, 2021 at 9:04
-
1$\begingroup$ For randomly chosen matrices that are not inverses of one another, this is O(n^2), which is worse than the O(n) method given in einpoklum's answer. $\endgroup$– user20095Commented May 28, 2021 at 20:13
-
1$\begingroup$ @BenCrowell The algorithm described in this answer is guaranteed to succeed with high probability no matter the inputs. The method in einpoklum's answer will succeed for "most" inputs, but only under certain assumptions about the distribution of the inputs, so it's not really a correct answer to the OP's question. $\endgroup$ Commented May 29, 2021 at 22:03
$\begingroup$
$\endgroup$
6
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 probability.
- If $A \times B$ is close to $I$, you don't care
If you can live with my relaxation** , then here's your test: repeatedly compute a random cell of $AxB$ and check it against $I$. That is, repeatedly:
- Uniformly sample a row index $i$.
- Uniformly sample a column index $j$.
- Compute the inner product of the $i$'th row of $A$ by the $j$'th column of $B$.
- Ensure the result is 0 for $i \neq j$ or 1 for $i = j$.
Each repetition takes $\Theta(n)$ time, and the number of repetitions depends on your distance parameter and the desired probability of being correct, only. And it's one-sided error too :-)
You could go even further, and estimate the inner product instead of computing it fully, by repeatedly sampling pairs of corresponding elements in the two vectors, multiplying just the pair, and taking an average over these individual element multiplications. The expected value of a single-element-pair multiplication is in fact the overall inner product (easy exercise). This will reduce your time complexity from $\Theta(n)$ to $O(1)$ (times a function of the distance parameter and desired correctness probability), but now the test has two-sided error.
(*) - This should work w.r.t. $L_k$ norms with $k > 0$. If you don't know what these are, see here.
(**) - This relaxation is the object of study of the field of Property Testing.
-
$\begingroup$ For randomly chosen matrices, this takes O(n) time to prove that they're not inverses. But for matrices that really are inverses of one another, won't this be $O(n^3)$? This seems like a smart thing to do for initial screening, but if it passes the first couple of samples, you probably want to switch to some other method. $\endgroup$– user20095Commented May 28, 2021 at 20:07
-
1$\begingroup$ @BenCrowell: No, I believe you misunderstood what I suggested. Mine is a probabilistic method. You never actually prove anything. $\endgroup$ Commented May 28, 2021 at 21:52
-
1$\begingroup$ To add to what einpoklum said, in probabilistic method we need to consider how quick the method achieves certain probability when comparing the time complexity. So if one method requires less number of operations to reach the same error rate as another method, the former is better. $\endgroup$– justhalfCommented May 28, 2021 at 23:34
-
1$\begingroup$ Given a fixed number of samples shouldn't the expected error increase as
nincreases due to the proportionally lower sample size? So to maintain a constant correctness probability asnincreases this would have to be something >O(1)(perhaps still lower thanO(n)but I don't know) $\endgroup$– DaveCommented May 29, 2021 at 13:26 -
1$\begingroup$ As a contrived concrete example, if I pick a sample size of 100 products each comprising 10 tested elements, then for
n=12that's going to test nearly the whole matrix, but forn=10000it will test a tiny fraction of it. I would trust its correctness forn=12much more than forn=10000. $\endgroup$– DaveCommented May 29, 2021 at 13:32
$\begingroup$
$\endgroup$
Multiply row 1 of A by column 1 of B. For randomly chosen matrices, this has unit probability of proving that they're not inverses, and you're done in O(n) time.
Find any eigenvalue and the corresponding eigenvector of A. I think this is O(n^2) (quicker than finding all eigenvalue-eigenvector pairs). Check whether this eigenvector is also an eigenvector of B, with the inverse eigenvalue. If not, then you're done.
Repeat 2 with an eigenvector that's orthogonal to the one found previously. Keep going until it becomes advantageous to switch and do...
In the space orthogonal to all the previously found eigenvectors, do matrix multiplication.