Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The simple proof goes:

Let B be the left inverse of A, C the right inverse.

C = (BA)C = B(AC) = B

This proof relies on associativity yet does not give any insight as to why this surprising fact about matrices is true.

AC means a bunch of linear combinations of of columns of A. CA means a bunch of linear combinations of rows of A. Completely different numbers get multiplied in each case.

The proof above is just a bunch of syntactical steps not having much to do with matrices directly, I cannot see how CA=AC=I.

Can anyone shed some light on this?

share|improve this question
6  
No, you are missing the forest for the trees: It works for matrices specifically because it works for any function, and matrices are just one kind of function. Matrices are a special case, so it works "for matrices specifically" because it always works for functions. It's not "hiding the reason it works for matrices", it's explaining the reason it works for matrices: because matrices are "really" functions, and this is a property of functions. –  Arturo Magidin Oct 20 '11 at 19:04
7  
More interesting is why a square matrix is left-invertible iff it is right-invertible. –  Yuval Filmus Oct 20 '11 at 19:09
3  
You keep missing my point: I "understand" because I know that $A$ is really a function, so as soon as you know that it has inverses on both sides, the inverses have to be the same one; it's not about "recipes", it's about correspondences: the matrix $A$ is a one-to-one onto correspondence; the matrix $C$ is the exact same correspondence "pointing the other way". So of course if you first go and then come back along the same route you will not have moved, and likewise, if you first come and then go back along the same route you will not have moved. –  Arturo Magidin Oct 20 '11 at 19:17
7  
@Leo: If you think I'm talking commutativity, then you aren't understanding what I'm saying. –  Arturo Magidin Oct 20 '11 at 19:31
2  
FWIW: I would love this question if it asked why (intuitively) a left inverse of a square matrix implies a right inverse. That left and right inverses are equal (if they both exist) definitely strikes me as a function thing. –  Jack Schmidt Oct 20 '11 at 19:43
show 7 more comments

2 Answers

up vote 17 down vote accepted

In fact, this isn't about matrices per se, but about inverses in general, and perhaps more specifically about inverses of functions. The same argument works for any function that has a left and a right inverse (and for elements of a monoid or ring, though these can also be interpreted as "functions" via an appropriate setting).

If you really want to try to understand the proof in terms of "meaning", then you should not think of matrices as a bunch of columns or a bunch of numbers, but rather as functions, i.e., as linear transformations.

Say $A$ is an $m\times n$ matrix; then $A$ is "really" a linear transformation from $\mathbb{R}^n$ to $\mathbb{R}^m$: the columns of $A$ are the images of the standard basis vectors of $\mathbb{R}^n$ under the transformation. If $B$ is a right inverse of $A$, then $B$ is $n\times m$, and $AB$ acts like the identity transformation on $\mathbb{R}^m$. In particular, $AB$ has to be onto, so the rank of $AB$ is $m$; since the rank of $AB$ is at most the rank of $A$, then the rank of $A$ has to be $m$; since the rank of $A$ is at most $\max(m,n)$, then $m\leq n$. This tells us that $A$ is onto (full rank), and that it has at least as many columns as it has rows.

If $C$ is a left inverse of $A$, then $C$ must be an $n\times m$ matrix, and $CA$ acts like the identity on $\mathbb{R}^n$. Because $CA$ is one-to-one, then $A$ has to be one-to-one. In particular, it's nullspace is trivial. That means that it cannot have more columns than rows (that would require a nontrivial nullspace, by the Rank-Nullity Theorem); since it has at least as many columns as it has rows, $A$ has exactly the same number of columns as rows, so $m=n$.

Moreover, $A$ is now one-to-one and onto. So it is in fact bijective. So it is in fact invertible. Invertible matrices have unique inverses by definition, so $B$ and $C$ have to be equal: they have no choice in the matter. It isn't about the details of the "recipe", it's about the properties of functions: once you have a function that is one-to-one and onto, it has an inverse and the inverse is unique.


I honestly think that trying to puzzle out the details of the "recipe" is not insightful here: it is staring at the bark of a single tree instead of trying to appreciate the forest.

But if you must (and I really think you shouldn't), then you want to realize that $AC$ and $CA$ are talking in a different language: the columns of $A$ specify a basis, $\gamma$, and tell you how to express the elements of $\gamma$ in terms of the standard basis $\beta$; it provides a "translation" from $\gamma$ to $\beta$. That is, $A=[\mathrm{Id}]_{\gamma}^{\beta}$. The inverse, $C$, explains how to express the elements of the standard basis $\beta$ in terms of the vectors in $\gamma$, $C=[\mathrm{Id}]_{\beta}^{\gamma}$. $AC$ talks in the language of the standard basis $\beta$, $CA$ talks in the language of $\gamma$. Then it becomes clear why "the same recipe" (not really) should work. It's not really the same recipe, because in $CA$ you "hear" vectors in $\gamma$, translate them into $\beta$, and then translates them back in to $\gamma$. But in $AC$ you "hear" vectors in $\beta$, translate them into $\gamma$, and then back into $\beta$. The "translation recipes" are the same, whether you do $\beta\to\gamma$ first or you do it second (translating English to Russian is the same, whether you are translating something written originally in English into Russian, or something that was translated into English first).

$A$ establishes a bijection between the vectors expressed in terms of $\gamma$, and the vectors expressed in terms of $\beta$. $C$ is the bijection going "the other way". Both $AC$ and $CA$ are the identity, but they are the identity of slightly different structures: $AC$ is the identity of "$\mathbb{R}^n$-with-basis-$\beta$", and $CA$ is the identity of "$\mathbb{R}^n$-with-basis-$\gamma$." Only when you forget that $AC$ and $CA$ are being interpreted as matrices on vector-spaces-with-basis do you realize that in fact you have the same "formula" for the expressions (i.e., that both matrices are "the" identity matrix).

If you want to stare at the bark so intently that you must think of matrices in terms of "linear combinations of rows" or "linear combinations of columns", you are going to miss a lot of important properties for matrices. Matrices are really functions; multiplication of matrices is really composition of functions. The aren't a bunch of vectors or a bunch of numbers thrown into a box that you multiply based on some ad hoc rule. They are functions.

Compare how easy, and, yes, intuitive, it is to realize that matrix multiplication is associative because it is just "composition of functions", vs. figuring it out by expanding the double summations of an entry-by-entry expression of $(AB)C$ and $A(BC)$: you are going in the wrong direction for 'intuitive' understanding. Staring at those summations will not tell you why multiplication is associative, it will only tell you it is. Trying to puzzle out why a right inverse is also a left inverse in terms of "adding columns" and "adding rows" is not going to help either: you need to think of it in terms of functions.

share|improve this answer
    
Haha, I think your answer to my question is "It is not intuitive that AC=CA." Unfortunately, I find your 3rd to last paragraph convincing and shall abandon my childhood dreams. –  Jack Schmidt Oct 20 '11 at 20:27
    
@Jack: I guess it's the same kind of fudging as we do when we say that two matrices are similar if "they represent the same linear transformation"; if you try to think of them in terms of "linear transformations on $\mathbb{R}^n$" then that doesn't really make sense. –  Arturo Magidin Oct 20 '11 at 20:36
    
@Jack: I've been trying to think if I can come up with something. Perhaps one can do it "non-canonically" through the dual space, at least in the real case: if we think of an invertible matrix $A$ as describing, via its columns, how to express vectors of a basis $\gamma$ in terms of the standard basis, then the rows of $A$ will describe how to express vectors of the dual of the standard basis in terms of the dual basis $\gamma^*$. Perhaps it's possible to carry it through in that light. –  Arturo Magidin Oct 21 '11 at 3:02
    
But a matrix can represent many other things too: a description of the adjacency relations in a graph, a system of linear equation, the transition states in a Markov process, etc. Does your interpretation make sense when extended to all these other cases? –  gary Oct 21 '11 at 3:30
2  
Sorry, I was looking for the model-specific explanation. Axioms and theory are what I tried escaping from. Thanks for the effort though. –  Leo Oct 23 '11 at 18:11
show 22 more comments

Arturo's response above is a very good one-as usual-but here's another way to approach the problem: Since the set of invertible n x n matrices is a non-commutative group under matrix multiplication, what you're really asking is why the right inverse of every element in a group is also a left inverse. This property is really true because the set of invertible matrices is a group and it's true of groups in general.

If you're unfamiliar with algebra, a group is defined as follows: A group is a set, G, together with an binary operation (i.e. a function from GxG into G) • (called the group law of G) that combines any two elements a and b to form another element, denoted a • b or ab. To qualify as a group, the set and operation, (G, •), must satisfy four requirements known as the group axioms: i)Closure: For all a, b in G, the result of the operation, a • b, is also in G. ii)Associativity:For all a, b and c in G, (a • b) • c = a • (b • c). iii)Identity element:There exists an element e in G, such that for every element a in G, the equation e • a = a • e = a holds. The identity element of a group G is often written as 1 or 1G, a notation inherited from the multiplicative identity. iv)Inverse element: For each a in G, there exists an element b in G such that a • b = b • a = 1. It's pretty easy to prove the set of all invertible n x n matrices is a group under matrix multiplication. Notice it's usually assumed in the definition that the identity is unique and 2 sided and each inverse of every element is 2 sided and unique to the element. However, it's not necessary to do so. One can modify the axioms of a group so it's not assumed the inverses are 2 sided: i.e. Define a group G to be nonempty set closed under a associative binary operation * such that 1) there exists at least one element e for all elements a in G such that e*a = a and 2) for every element a, there is at least one element b such that b*a= e. You can of course, alternatively define an identity on the right and inverses on the right. The point here is to not assume the 2 sided-ness of the identity and the inverses and you should try and prove that every left identity(inverse) must also be a right.You then prove that each left is unique and so is every right-therefore, they're equal. It's a bit tedious, but I think you'll find it to answer your question in a decisive fashion.

Another way-consider the following:Modify the above definition of a group so that e is a LEFT identity and for every element, there is a right inverse. Is the resulting set under a binary operation a group? It turns out the answer is NO. For a counterexample, define a*b=b for all a and b in the group. Then we can pick any e to be the left identity of all the elements. Similarly, any b has the right inverse e because b*e=e.In the trivial case of a group-a single element e-this is clearly a group. BUT if there is more than one element, the result is NOT a group: If a*x=a and b*x=b, then x=a and x=b, which obviously can't hold in the general case because there is no single (two-sided) identity element!

Do the exercise above in the alternate definition of a group with the weaker axioms-this plus the counterexample should clear the fog of your confusion.

share|improve this answer
3  
I don't understand your point. What is the definition of invertible matrix you're using? If you want to check the weaker axioms only requiring one-sided inverses (identity and associativity are clear anyway) then you actually have to prove something: if $A$ is a right invertible matrix and $B$ is its right inverse then why does $B$ admit a right inverse itself? I don't think that that's what is being asked here. –  t.b. Oct 20 '11 at 21:49
3  
@Mathemagician1234 : I think you are missing the point of the question. The OP is clearly aware that invertible matrices form a group -- in the question statement, he gave the usual group-theoretic proof that a left inverse and a right inverse have to be equal (using associativity). Adding the word "group" to this does not clarify anything. –  Adam Smith Oct 21 '11 at 3:13
4  
@Mathemagician1234 : I have no idea whether the OP knows the word "group", but he knows the "group-theory proof" that left and right inverses agree. I don't see how your explanation adds anything non-linguistic to his understanding. –  Adam Smith Oct 21 '11 at 3:34
6  
If you think your comments 'challenge' anything apart from the image of yourself that you choose to present to other users of this site, I think you are mistaken. –  Mariano Suárez-Alvarez Oct 21 '11 at 22:46
4  
@Mathemagician1234: you have to be civil independently of anything. –  Mariano Suárez-Alvarez Oct 22 '11 at 12:35
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.