0
$\begingroup$

I have found this question How to prove that the inverse of a matrix is unique?

And while the accepted answer is fine I was wondering if it's possible to proof the uniqueness by algorithm.

There is an algorithm for calculating the inverse of the matrix and if the algorithm is exactly defined in each step e.g. no randomness is add, is it enough to prove uniqueness. My reasoning is that in each step of algorithm there is exact way to next step. For each input I you always get same output O.

Is this enough as a proof?

$\endgroup$
3
  • 2
    $\begingroup$ There is no strict correlation between the uniqueness of the solution of a problem and the uniqueness of the algorithm for calculating such a solution. First of all, we need a precise definition of algorithm ... Having said that, if I have an algorithm $A_0$ made of a finite set of rules precisely speciifed, I can always add some unnecessary operation such that the new algorithm $A_1$ is "formally" different from the previous one and still produce the same result. $\endgroup$
    – Mauro ALLEGRANZA
    Commented May 23, 2014 at 7:38
  • $\begingroup$ I suggest you do some reading about how the 4-color map theorem was proved. It's a very interesting story and fairly relevant to the topic you're asking about. $\endgroup$
    – Pockets
    Commented May 23, 2014 at 8:15
  • $\begingroup$ The algorithm will give an unique solution, showing that it is the only one is another matter $\endgroup$
    – vonbrand
    Commented May 23, 2014 at 9:25

5 Answers 5

Reset to default
4
$\begingroup$

You can generally prove existence by algorithm, but it is far more difficult to prove uniqueness a priori. You just show that your algorithm is determinist and always find the same solution given the same input, but how do you prove there doesn't exist other ways to find other solutions ? For example, extended Euclidian algorithm find Bezout's coefficients, but they are not unique...

$\endgroup$
2
$\begingroup$

This is not a proof. The algorithm may only give one result for any given input, but that doesn't prove that no other matrices would be inverses of the input. Strictly speaking, it doesn't even prove that the output of the algorithm is an inverse of the input; until you prove the algorithm's correctness, you've just got some matrix.

$\endgroup$
1
$\begingroup$

Strictly speaking you can't consider algorithm as a proof of uniqueness. Algorithm is only the way how to get inverse matrix, but it did not give answer question about uniqueness. You can have different algorithm, which can give different result. By the way. The proof of uniqueness of inverse matrix is easy proof. Look at arbitrary textbook of linear algebra or abstract algebra (chapters about groups). Invertible matrices of order $n$ over field $K$ forms General Linear Group. And in every group has equation $A.X=B$ unique solution(but multiplication is not commutative!). Go with that proof in that way, it is much more easier than using some algorithms.

$\endgroup$
1
$\begingroup$

Yes, you can prove uniqueness by algorithm. If you prove that every possible solution is an output of your algorithm, and your algorithm can only produce one output, then the solution must be unique (if it exists).

The usual matrix inversion algorithm is an algorithm to compute an equation that is equivalent to $AX = I$: each step of the algorithm computes equivalent equations, so the solution set to the input $AX = I$ and the solution set to the final output $X = B$ of the algorithm are the same. Since $X=B$ obviously has a unique solution, it must also be the unique solution to $AX = I$.

$\endgroup$
0
$\begingroup$

If you are only allowed to use "this" algorithm and this algorithm is deterministic then certainly there is only one possible solution to each problem resulting from using "this" algorithm. The problem is that an algorithm is not unique. Take finding the inverse of a matrix. There are numerous algorithms for finding the inverse of a matrix. There are two questions you might ask: $1$) do they always lead to the same solution and $2$) is there a way to show they are equivalent (those two questions are basically equivalent).

Consider an algorithm which takes a list of (unique) words and finds the longest word from the list. Let's say the list is $\{The, cat, can, not, has, a, nut\}$. Depending on the algorithm you may get many different solutions such as $cat$, $has$, $nut$, etc. I can present a deterministic algorithm such as read through the list in order, count the letters and if the number of letters is greater than the current maximum then overwrite the current maximum. This algorithm is deterministic yet the problem certainly does not have a unique solution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .