If $AB = I$ then $BA = I$

111,371

Solution 1

Dilawar says in 2. that he knows linear dependence! So I will give a proof, similar to that of TheMachineCharmer, which uses linear independence.

Suppose each matrix is $n$ by $n$. We consider our matrices to all be acting on some $n$-dimensional vector space with a chosen basis (hence isomorphism between linear transformations and $n$ by $n$ matrices).

Then $AB$ has range equal to the full space, since $AB=I$. Thus the range of $B$ must also have dimension $n$. For if it did not, then a set of $n-1$ vectors would span the range of $B$, so the range of $AB$, which is the image under $A$ of the range of $B$, would also be spanned by a set of $n-1$ vectors, hence would have dimension less than $n$.

Now note that $B=BI=B(AB)=(BA)B$. By the distributive law, $(I-BA)B=0$. Thus, since $B$ has full range, the matrix $I-BA$ gives $0$ on all vectors. But this means that it must be the $0$ matrix, so $I=BA$.

Solution 2

So you want to find a proof of this well-known fact, which avoids the usual "indirect" proofs? I've also pondered over this some time ago.

We have the following general assertion:

Let $M$ be a finite-dimensional $K$-algebra, and $a,b \in M$ such that $ab=1$, then $ba=1$. [For example, $M$ could be the algebra of $n \times n$ matrices]

Proof: The sequence of subspaces $\cdots \subseteq b^{k+1} M \subseteq b^k M \subseteq \cdots \subseteq M$ must be stationary, since $M$ is finite-dimensional. Thus there is some $k$ and some $c \in M$ such that $b^k = b^{k+1} c$. Now multiply with $a^k$ on the left to get $1=bc$. Then $ba=ba1 = babc=b1c=bc=1$. QED

No commutativity condition is needed. The proof shows more general that the claim holds in every left- or right-artinian ring $M$.

Remark that we needed, in a essential way, some finiteness condition. There is no purely algebraic manipulation with $a,b$, which shows $ab = 1 \Rightarrow ba=1$ (and shift operators provide a concrete counterexample). Every argument uses some argument of the type above. For example when you want to argue with linear maps, you have to know that every subspace of a finite-dimensional(!) vector space of the same dimension actually is the whole vector space, for which there is also no "direct" proof. I doubt that there is one.


PS. See here for a proof of $AB=1 \Rightarrow BA=1$ for square matrices over a commutative ring.

Solution 3

If $\rm\,B\,$ is a linear map on a finite dimensional vector space $\rm\, V\,$ over field $\rm\,K,\,$ then easily by finite dimensionality (cf. Note below) there is a polynomial $\rm\,0\ne p(x)\in K[x]\;$ with $\rm\,p(B) = 0.\,$ W.l.o.g.$\rm\,p(0) \ne 0\,$ by canceling any factors of $\rm\,B\;$ from $\rm\;p(B)\;$ by left-multiplying by $\rm A,\,$ using $\rm\, AB = 1.$

Notice $\rm\ AB=1 \, \Rightarrow\, (BA-1)\, B^n =\, 0\;$ for $\,\rm\;n>0\;$

so by linearity $\rm\, 0 \,=\, (BA-1)\ p(B)\, =\, (BA-1)\ p(0) \;\Rightarrow\; BA=1 \quad\quad$ QED

This is essentially a special case of computing inverses by the Euclidean algorithm - see my Apr 13 1999 sci.math post on Google or mathforum.

Note $ $ The existence of $\rm\;p(x)\;$ follows simply from the fact that $\rm\,V\;$ finite-dimensional implies the same for the vector space $\rm\,L(V)\,$ of linear maps on $\rm\,V\,$ (indeed if $\rm\,V\;$ has dimension $\rm n$ then a linear map is uniquely determined by its matrix of $\,\rm n^2\,$ coefficients). So $\rm\, 1,\, B,\, B^2,\, B^3,\,\cdots\;$ are $\rm\,K$-linearly dependent in $\rm\, L(V)$ which yields the sought nonzero polynomial annihilating $\rm\,B.$

Solution 4

Let $x_1, x_2, \dots, x_n$ be a basis of the space. At first we prove that $Bx_1, Bx_2, \dots, Bx_n$ is also a basis. To do it we need to prove that those vectors are linearly independent. Suppose it's not true. Then there exist numbers $c_1, c_2, \dots, c_n$ not all equal to zero such that $$c_1 Bx_1 + c_2 Bx_2 + \cdots + c_n B x_n = 0.$$ Multiplying it by $A$ from the left, we get $$c_1 ABx_1 + c_2 ABx_2 + \cdots + c_n ABx_n = 0,$$ hence $$c_1 x_1 + c_2 x_2 + \cdots + c_n x_n = 0$$ and so the vectors $x_1, x_2, \dots, x_n$ are also linearly dependent. Here we get contradiction with assumption that the vectors $x_i$ form a basis.

Since $Bx_1, Bx_2, \dots, Bx_n$ is a basis, every vector $y$ can be represented as a linear combination of those vectors. This means that for any vector $y$ there exists some vector $x$ such that $Bx = y$.

Now we want to prove that $BA = I$. It is the same as to prove that for any vector $y$ we have $BAy = y$. Now given any vector $y$ we can find $x$ such that $Bx = y$. Hence $$BAy = BABx = Bx = y$$ by associativity of matrix multiplication.

Solution 5

Since there seem to be some lingering beliefs that an approach which does not make explicit use of the finite-dimensionality could be valid, here is a familiar counterexample in the infinite dimensional case.

Let $V = \mathbb{R}[t]$ be the vector space of real polynomial functions. Let $B: V \rightarrow V$ be differentiation: $p \mapsto p'$, and let $A: V \rightarrow V$ be anti-differentation with constant term zero: $\sum_{n=0}^{\infty} a_n t^n \mapsto \sum_{n=0}^{\infty} \frac{a_n}{n+1} t^{n+1}$.

These are both $\mathbb{R}$-linear maps and $B \circ A$ is the identity, but $A \circ B$ is not (the constant term is lost).

Share:
111,371

Related videos on Youtube

Dilawar
Author by

Dilawar

Updated on March 26, 2022

Comments

  • Dilawar
    Dilawar over 1 year

    If $A$ and $B$ are square matrices such that $AB = I$, where $I$ is the identity matrix, show that $BA = I$.

    I do not understand anything more than the following.

    1. Elementary row operations.
    2. Linear dependence.
    3. Row reduced forms and their relations with the original matrix.

    If the entries of the matrix are not from a mathematical structure which supports commutativity, what can we say about this problem?

    P.S.: Please avoid using the transpose and/or inverse of a matrix.

    • Bill Dubuque
      Bill Dubuque over 11 years
    • littleO
      littleO over 9 years
      Suppose $U$ and $V$ are sets and $T:V \to W$ is a function. Then $T$ has a left inverse $\iff$ $T$ is one-to-one, and $T$ has a right inverse $\iff$ $T$ is onto. Suppose now that $V$ is a finite dimensional vector space, and $T:V \to V$ is a linear transformation. Then $T$ has a left inverse iff $T$ is one-to-one iff $T$ is onto iff $T$ has a right inverse. From here, it's easy to show that any left inverse must also be a right inverse. (If $LT = I$ and $TR = I$, then $LTR = L \implies R = L$.)
    • linear_combinatori_probabi
      linear_combinatori_probabi about 5 years
      @littleO: Is your $U$ meant $W$?
    • SOFe
      SOFe over 4 years
      @BillDubuque what's up with the link? It's linking back to this question.
    • Bill Dubuque
      Bill Dubuque over 4 years
      @SOFe Alas, after 7 years, I don't recall what link was actually intended there. But hopefully the name will aid in keyword searches.
    • robjohn
      robjohn over 3 years
      A comment to Why are Dedekind-finite rings called so? has a link back to this question. Perhaps that was the link intended in the first comment here.
  • Dilawar
    Dilawar about 13 years
    Thanks Martin. Though I have to get accustomed to some of the words you used but certainly, this improved my understanding and I have one more approach in my list.
  • Martin Brandenburg
    Martin Brandenburg about 13 years
    1+. Then I also add the following example, because I think it is easier (but very similar): Consider the vector space of infinite sequences (of rational numbers, say), and the linear maps $A : (a_0,a_1,...) \to (0,a_0,a_1,...), B : (a_0,a_1,...) \to (a_1,a_2,...)$. Then $BA=1$, but not $AB=1$ since $AB$ maps $(a,0,...) \mapsto 0$. You may also restrict to finite sequences (without fixed lenght) and then cook up infinite matrices satisfying the properties.
  • Pete L. Clark
    Pete L. Clark about 13 years
    @MB: This is a very nice answer. A couple of tips: (i) it took me several readings to gather that "quadratic matrix" = "square matrix". This is included in the question, so it seems best to just assume it. (ii) I think you have some $A$'s which should be $a$'s (or vice versa). (iii) Since the OP asked for an elementary answer, please consider rewriting it to first treat exactly the case s/he asked for with no "fancy language" (ideals, Artinian algebras, etc.). Afterwards you can comment on how general your argument can be made.
  • Pete L. Clark
    Pete L. Clark about 13 years
    @MB: Right, it's similar -- and indeed, also has a polynomial interpretation, as I'm sure you know.
  • Martin Brandenburg
    Martin Brandenburg about 13 years
    You use the fact that a $n$-dimensional subspace of a $n$-dimensional vector space coindices with the vector space. This is not clear at all from the definitions, is false for cardinals $n$, and again uses some chain argument or similar arguments.
  • Pete L. Clark
    Pete L. Clark about 13 years
    @MB: I think this argument is okay. It is very standard in intro linear algebra classes to prove that in a finite-dimensional vector space every spanning set contains a basis and every LI set can be enlarged to a basis. Moreover the proofs are algorithmic and the algorithm is always the same: row reduction.
  • Laurent Lessard
    Laurent Lessard about 13 years
    "The claim is also true for non-square matrices". No it is not.
  • Davidac897
    Davidac897 about 13 years
    @Martin: I'm assuming $n$ is finite - maybe I should have been more explicit. I was assuming that the fact about $n$ dimensional subspaces coinciding with the original space was elementary enough to fit under his requirements.
  • Davidac897
    Davidac897 about 13 years
    Besides, Martin's proof also uses this fact (how else can you show that the chain is stationary in a finite-dimensional vector space?).
  • Martin Brandenburg
    Martin Brandenburg about 13 years
    Yes I also use this or related statements and we have to use something like that; I just wanted to make precise for the readers what you are using.
  • Dilawar
    Dilawar about 13 years
    Thank you David. This is what exactly I've been looking for. @MB : I really appreciate the way you have formulate the solutions.
  • Martin Brandenburg
    Martin Brandenburg about 13 years
    Thanks for the suggestions. I've edited my answer.
  • Bill Dubuque
    Bill Dubuque about 13 years
    Compare to my proof here.
  • Bill Dubuque
    Bill Dubuque about 13 years
    @Pete: these are folklore results, e.g. see the references in my post to papers of Vasconcelos et al from the seventies (but the results were surely known before then).
  • Bill Dubuque
    Bill Dubuque about 13 years
    see my post here which makes obvious the crucial role of finite dimensionality. See esp. the linked sci.math post.
  • Dilawar
    Dilawar about 13 years
    May be by the end of this semester, I'll be able to understand it. I have added it into 'things to understand' list. Thanks!
  • Bill Dubuque
    Bill Dubuque about 13 years
    That paper invokes LU-factorization, which is quite a sledgehammer for a result that is really nothing but a pigeonhole squeezing argument (see my post).
  • Pierre-Yves Gaillard
    Pierre-Yves Gaillard about 13 years
    Very nice!!! I just suggest that you replace "from the leftwe get" with "from the left we get", and "and so vectors" with "and so the vectors".
  • falagar
    falagar about 13 years
    @Pierre-Yves Gaillard: Corrected, thank you.
  • Dilawar
    Dilawar about 13 years
    Thanks falagra ! I almost got it in the first read itself. :-) I think you missed something to point out in the first paragraph after last line. I think you need to add one more line stating 'A contradiction.'.
  • J. M. ain't a mathematician
    J. M. ain't a mathematician about 13 years
    Bill: LU decomposition is merely Gaussian elimination, rearranged, and I would suppose equivalent to row reduction, which the OP says he can use.
  • Bill Dubuque
    Bill Dubuque about 13 years
    That's essentially the proof that I gave - translated into the language of coordinates (bases). However, adding such extraneous information as bases only serves to obfuscate the simple essence of the manner, namely: injective maps cannot decrease heights (here = dimension = length of max subspace chain). As I stress in my post, the proof is a very intuitive one-line pigeonhole squeeze when viewed this way.
  • Bill Dubuque
    Bill Dubuque about 13 years
    @MB: Polynomials give a nice concrete model: Q[x] where the right shift is R = x = multiplication by x, and left shift L = (f(x)-f(0)/x. Then LR = I but RL f(x) = f(x)-f(0), so RL != I. For more see my old post bit.ly/Shift1-1notOnto
  • J. M. ain't a mathematician
    J. M. ain't a mathematician about 13 years
    +1, and to add: Row reduction/Gaussian elimination/LU decomposition is just a left multiplication of a matrix by a sequence of so-called "Gauss transforms", which are low-rank corrections to the identity matrix. Nothing sledgehammer-y about it!
  • Tsuyoshi Ito
    Tsuyoshi Ito about 13 years
    Nice proof, but why do you write a proof of BA=I⇒AB=I when the question asks a proof of AB=I⇒BA=I? (Of course this difference is inessential.)
  • Pierre-Yves Gaillard
    Pierre-Yves Gaillard about 13 years
    I think it's the best answer so far. It only uses the fact that a system of linear equations with more unknowns than equations has a nontrivial solution. Alternative wording: There is a polynomial q such that q(B) = 1, q(0) = 0. Then BA-1 = (BA-1) q(B) = 0.
  • Bill Dubuque
    Bill Dubuque about 13 years
    Thanks for the comments. I swapped A,B to match the OP's notation. My posts here are excerpts of my linked sci.math posts (which had A,B swapped). They're part of a handful of posts that I composed to provide different perspectives on this FAQ.
  • Bill Dubuque
    Bill Dubuque about 13 years
    @J.M. That doesn't stop it from being a sledgehammer compared to some other proofs given here. Not only are they simpler but more conceptual. I think the OP could easily understand at least one of those proofs.
  • Mariano Suárez-Álvarez
    Mariano Suárez-Álvarez about 13 years
    @Bill, the thing is, «the essence of the matter» is not always, and is not for everybody, the best way to see something; obfuscation is in the eye of the beholder. I enjoyed reading through each of your proofs, but I find it quite natural that they be classified in the may-be-by-the-end-of-this-semester-I'll-be-able-to-understan‌​d-it category!
  • Bill Dubuque
    Bill Dubuque about 13 years
    @Mariano. But it is important to point out the essence of the matter since rarely do textbook authors do so. Even if a student is not able to completely grasp the essence now, the seed will have been planted to make the "Aha!" moment germinate when the time is ripe. See my latest post here where I have stressed more clearly the innate essence, namely that 1-1 not onto maps lead to infinite descending subspace chains, i.e. Dedekind infinite => infinite dimension. This can easily be comprehended by a novice if explained very carefully.
  • Bill Dubuque
    Bill Dubuque about 13 years
    @Dilawar: I've reformulated this proof to make it clearer. Please see my other post here which shows that it essentially reduces to Hilbert's infinite hotel on subspaces, viz. math.stackexchange.com/questions/4252
  • Bill Dubuque
    Bill Dubuque about 13 years
    @Dilawar / readers: This is a reformulation of my prior pigeonhole proof intended to make clearer the essence of the matter. Please feel free to ask questions if anything is not clear.
  • Dan Ramras
    Dan Ramras about 13 years
    I'm presenting this in class soon, and this is basically what I plan to say. But the first part can be phrased just in terms of row reduction (which makes it fit earlier in a course). Consider the equation Bx=0. Multiplying by A, we have ABx=0, i.e. x = 0. So B has linearly independent columns, and its reduced eschelon form is the identity matrix. That means the equation Bx=z always has a solution, and now you can continue as above.
  • Admin
    Admin over 9 years
    The Google Groups link no longer works, it seems; here's a replacement.
  • Martin Brandenburg
    Martin Brandenburg over 9 years
    The proof shows: If $A$ is a $K$-algebra containing two elements $a,b$ such that $ab=1$ and $b$ is algebraic over $K$, then $ba=1$.
  • Bill Dubuque
    Bill Dubuque over 9 years
    @Martin Right. In attempt to make the answer as accessible as possible, I purposely avoided any further abstraction.
  • Andrew D. Hwang
    Andrew D. Hwang almost 9 years
    This is nice! However, it appears you can avoid Claims 3 and 4 (and, in particular, the induction): Since $A$ is a product of elementary matrices, $A$ is invertible, so you can just conjugate $AB = I$ by $A$, to get $BA = A^{-1}(AB)A = I$. :)
  • goblin GONE
    goblin GONE about 8 years
    This potentially works over any commutative ring, not just a field, right? Explicitly, I think the following holds: Suppose $R$ is a commutative ring and that $V$ is an $R$-module that has a finite chain of subspaces of maximum length among all chains of subspaces. Then left-injective elements of $\mathrm{End}(V)$ should also be left-surjective.
  • Patrick Abraham
    Patrick Abraham almost 7 years
    Isn't this only a proof for the existence of a right and left inverse?
  • Mark
    Mark over 6 years
    @PatrickAbraham: Yes, but this is easy. See littleO's comment to the question.
  • Bill Dubuque
    Bill Dubuque over 6 years
    The prior link is now stale. Here are working versions: mathforum or Google groups
  • Peter
    Peter over 5 years
    Why $AB$ has full rank imply $B$ has full rank ? I would say if $AB=I$ then $B$ in one to one and $A$ is full rank (if $f$ invertible at right, then $f$ is surjective, and if $f$ invertible at left, then $f$ in injective). @Davidac897
  • Davidac897
    Davidac897 over 5 years
    @Peter The subsequent sentence explains how the implication works.
  • ashpool
    ashpool over 3 years
    Beautiful. I think this is probably the most elementary proof possible, which uses only row operations and matrices.
  • Ben Grossmann
    Ben Grossmann over 3 years
    I know this an old post, but maybe somebody can answer the following. We can only say that $(BA-1)\ p(0) = 0 \;\Rightarrow\; BA=1$ if we know that $p(0)$ has full row rank (i.e. $p(0)$ is not a zero-divisor from the right). However, all we know about $p(0)$ per the setup is that $p(0) \neq 0$. Is this a flaw in the proof? If so, is there a way to fix the proof?
  • Peter Franek
    Peter Franek about 3 years
    But you are still implicitely using some nontrivial statements from linear algebra such as dimension n subspace of dimension n space is the full space. Otherwise, how do you justify finiteness of the chain?
  • Christoph
    Christoph about 3 years
    @BenGrossmann $p\in K[x]$ so $p(0_K)\in K$ and $p(0_{\operatorname{End}(V)})=p(0_K)\cdot \operatorname{id}_V$.
  • Ben Grossmann
    Ben Grossmann about 3 years
    @Christoph Not sure how I had missed that, thanks.
  • Martin Brandenburg
    Martin Brandenburg over 2 years
    I use that the dimension is a well-defined and that a proper subspace of a vector space has a smaller dimension. You call this non-trivial?
  • Arrow
    Arrow about 2 years
    Dear @BillDubuque, it seems that we really only need the lowest degree coefficient of the polynomial to be cancellable. If so, does the assertion hold for matrices over any (commutative) domain (by taking the characteristic polynomial and using Cayley-Hamilton)?
  • Max Herrmann
    Max Herrmann about 2 years
    Ping! Pinpoint.
  • Admin
    Admin almost 2 years
    Alternatively, rom the 2nd paragraph, since $\exists x;\, Bx = b,\,\forall b\Rightarrow \exists X;\,BX = I.$ Then, $AB = I\Rightarrow ABX = IX\Rightarrow A = X\Rightarrow BA = BX = I.$
  • Morad
    Morad almost 2 years
    Did you use the assumption that $A$ and $B$ are square?
  • Pietro Paparella
    Pietro Paparella almost 2 years
    Yes. It is stated in the paper immediately preceding theorem.