# Generalized inverse solution to system of linear equations proof

I'm going through a set of course notes for an introduction to the theory of linear models class at my university. Unfortunately, the professor who wrote this note set is no longer at this school, and I have no means of contacting him. So, I'm having trouble with a proof, and was looking for help.

Theorem 2.4
For an $m$ x $n$ matrix A, the matrix G is a generalized inverse of A if and only if G$y$ is a solution to A$x=y$ for every $m$ x $1$ vector $y$ that makes A$x=y$ a consistent system of linear equations.

I know that I must prove two statements:
1) Assume that G is a generalized inverse of A and show that this implies G$y$ is a solution to A$x=y$ whenever it is consistent.

2) Assume that G$y$ is a solution to A$x=y$ for every $y$ that makes the system consistent, then prove G is a generalized inverse of A.

The first part was rather trivial. I proved it, and my proof agreed with the one provided by the professor. However, for the life of me, I cannot prove (2). I've sat at my desk for two hours now trying. The proof provided by the professor seems entirely incorrect, too.

My attempt at a proof
All I have is restatement of the assumption. Let G be a solution to A$x=y$ whenever $y$ is such that the system is consistent.
Then AG$y$ = AGA$x$.

The solution
The professor cherry picks $y=a_j$, the jth column of A. Then says
AGA = AG$[a_1 ... a_n] = [a_1 ... a_n] =$A. Thus, G is a generalized inverse of A. QED.

This is wholly unsatisfactory in my opinion. What about all of the $y$ vectors that ARE NOT merely column vectors of A but for which A$x=y$ is still consistent? This proof says nothing of these cases.

Can someone please shed light on the correct method to prove the second statement?

• I am having trouble understanding why generalized inverse(s) were defined that way. Even wikipedia (en.wikipedia.org/wiki/Generalized_inverse) has a more rigorous definition, avoiding the word "consistent" which certainly needs to be defined in order to be understood safely and without misunderstandings. – Alecos Papadopoulos Jun 24 '15 at 19:29
• Hey Alecos, I do understand the definition of the word consistent. It means that Ax=y has at least one solution. However, that neither helps me in proving the second statement nor helps me to understand why the professor's proof is valid. – Patrick Jun 24 '15 at 19:46
• I guess I should add that I'm not very confused on the topic of the generalized inverse, rather this proof. – Patrick Jun 24 '15 at 19:46

The cherry-picking is the key idea. The point is that the condition "whenever $y$ is such that the system is consistent" is stronger than needed.

Note that there are $n$ $y$'s for which the system is obviously consistent: the columns of $A$. This is because with $x=x_i=(0,0,\ldots,0,1,0,\ldots,0)$, with a $1$ in position $i$, $Ax = a_i = y_i$.

Now it is not necessarily the case that $Ga_i = x_i$. Nevertheless, when you stack the columns $Ga_1, Ga_2, \ldots, Ga_n$ vertically, you obtain an $n\times n$ matrix--it's precisely $GA$, obviously--that when left-multiplied by $A$ must return the stack of columns $y_i$. But that's exactly $A$ itself, since $y_i=a_i$. We have just seen that $A(GA) = A$, QED.

For a little more intuition, note that the set of $y$ that make the system consistent is a vector space $V$ (the column space of $A$). Because what is to be proven is a consequence of various linear operations, it will suffice to demonstrate it on a generating set for $V$. An obvious, immediately available generating set consists of the columns of $A$ itself. Statement (2) could just as well have been written

Assume that $Gy$ is a solution to $Ax=y$ for every $y$ in a basis for the column space of $A$. Prove $G$ is a generalized inverse of $A$.

• Hey Whuber, thanks for your answer. I must admit, I'm still quite confused. I don't doubt that you are correct. However, I cannot at all see why you are. If I cherry pick the y's like you and my professor suggest to do, then arriving at AGA = A is trivial and obvious. I still do not see how that implies the same condition holds when Ax=y and y IS NOT a column of A. Can you explain how this is true? – Patrick Jun 24 '15 at 20:37
• Okay, I feel like a big idiot. Whuber, your answer makes a lot more sense. I think. Since y must lie in the column space of A, then the basis of that column space is either all of the columns or A or some subset of the columns. Thus when we prove G is a generalized inverse of A given the assumption Gy is a solution to Ax=y for every y, and, in particular when y is a column of A, we have shown it is true for every vector in the space, because every vector can be written as a linear combination of the basis vectors. Is this line of thought correct? – Patrick Jun 24 '15 at 20:43
• Yes, that is exactly right: now you understand. I was taught to think of this situation geometrically: $A$ maps $\mathbb{R}^n$ into its image, which is some sub-vector space of $\mathbb{R}^m$ (the "column space"). What matters about $G$ is what it does to that image: it needs to send its elements right back where they came from (modulo the kernel of $A$). Since $G$ is a linear transformation, it is determined by its values on any generating set of the image--such as any basis or (somewhat redundantly, perhaps) the set of columns of $A$. – whuber Jun 24 '15 at 20:47
• I've struggled mightily with the geometric interpretations of linear algebra. So that explanation helped out a lot. Thanks a ton, whuber. If I could give you more upvotes, I would. – Patrick Jun 25 '15 at 14:57