\( \newcommand{\bb}{\mathbb} \newcommand{\bf}{\mathbf} \newcommand{\cal}{\mathcal} \newcommand{\L}{\left} \newcommand{\R}{\right} \newcommand{\C}{\mathbb{R}} \newcommand{\F}{\mathbb{F}} \newcommand{\mat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\qed}{\quad\square} \newcommand{\opn}{\operatorname} \)

Interesting Problems

Exercise 1 (Source: Algebra (2nd edition) by Michael Artin – Chapter 1, Miscellaneous, Problem 8)
Consider a general system \(A X=B\) of \(m\) linear equations in \(n\) unknowns, where \(m\) and \(n\) are not necessarily equal. The coefficient matrix \(A\) may have a left inverse \(L\), a matrix such that \(L A=I_n\). If so, we may try to solve the system as we learn to do in school: \[ A X=B, \quad L A X=L B, \quad X=L B . \]

But when we try to check our work by running the solution backward, we run into trouble: If \(X=L B\), then \(A X=A L B\). We seem to want \(L\) to be a right inverse, which isn’t what was given.

NoteSolution (Solution to Exercise 1)

Solution (Solution to Exercise 1). The problem can be divided into two parts. The first part is solving the equation, where the second part is substituting back.

We first check the second part. Suppose for all \(B\), we have \(X=LB\). Let \(B\) equals \(\bf{e}_k\), then \(ALB\) is the \(k\)-th column of \(AL\). By equating \(B\) to \(\bf{e}_1,\bf{e}_2,\dots,\bf{e}_m\), we show that the \(k\)-th column of \(AL\) is \(\bf{e}_k\). Thus, \(AL\) is the identity matrix, meaning that \(L\) is \(A\)’s right inverse.

Since we prove the correctness of the second part, the mistake must occur in the first part. In fact, in our above derivation, we used the expression “for all \(B\).”
Is our equation consistent for all \(B\)? This must not be the case because it is not stated in the problem. Moreover, suppose \(n\neq m\), then \(A\) having a left inverse implies that there are more rows than columns, in which case there must exist some \(B\)s such that \(AX=B\) is inconsistent.

The problem is the step \(A X=B, \quad L A X=L B\). The equation \(LAX=LB\) is not equivalent to \(AX=B\). The logical relation here is \[AX=B \implies LAX=LB\] However, to solve an equation, we need an “if and only if” relation. What this tells is that for \(B\) such that \(AX=B\) is consistent, \(X\) equals \(LB\) and is therefore unique.

This is analogous to extraneous roots which results from solving equations using non-equivalent equations. Here are a few simple examples:

  1. \(\sqrt{x}=-1 \implies x=1\)
  2. \(\displaystyle\frac{1}{x-2}=3 \implies 3(x-2)=1\)