Is proof by algorithm credible?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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