TITLE: Row augmentation to solve for null-space vectors.
QUESTION [1 upvotes]: I'm looking to understand how a method of balancing chemical equations using the null space vectors of a row augmented matrix works (the method is outlined in detail in the following paper).
https://arxiv.org/ftp/arxiv/papers/1110/1110.4321.pdf
I understand how to do the process and I understand why the null space vector would give me the desired coefficients. However, I don't understand how this augmentation procedure produces the null vectors. Why does adding a number of rows equal to the nullity, such that the rows form an identity submatrix in the right corner, give the null space vectors of the original matrix upon inversion? In the paper, they don't make it clear why this procedure produces the null space vectors.
EDIT: Here is the procedure up to where I'm encountering problems.

(a) Construct a chemical-composition matrix for the
  chemical-reaction equation.
  (b) Determine the nullity, or dimensionality, of the matrix
  null space of the chemical- composition matrix.
  (c) Augment the matrix with a number of rows equal to the
  nullity number. (My Note: the rows should form an identity submatrix in the bottom right corner)
  (d) Compute the matrix inverse of the augmented matrix by
  using the built-in functions of a scientific calculator or
  computer spreadsheet program.
  (e) Extract the null-space basis vectors from the inverted
  matrix. (The vectors will be the columns at the far right of
  the inverted matrix; the number of columns included—0,
  1 or more—should equal the nullity of the row-echelon
  matrix.) This defines the null space of the original
  chemical-composition matrix!" (emphasis mine) 

What I currently don't understand is how "e" follows from "c" and "d". Why does augmenting as detailed in "c" and inverting as detailed in "d" give the null space vectors of the original matrix as is stated in "e"?

REPLY [2 votes]: The trick described in the paper is handy, but it doesn’t work in general. Obviously, the original matrix $M\in\mathbb R^{m\times n}$ must have more columns than rows. In addition, it must have full rank. If not, you’ll end up with a singular matrix after padding, but with no good way to tell a priori which row(s) are redundant. There’s a more subtle constraint as well. If the padded matrix is nonsingular, then we have $$M_{\text{pad}}^{-1}=\left[\begin{array}{c|c}A & B \\ \hline 0 & I_{n-m}\end{array}\right]^{-1}=\left[\begin{array}{c|c}A^{-1} & -A^{-1}B \\ \hline 0 & I_{n-m}\end{array}\right],\tag{*}$$ which implies that the first $m$ columns of $M$ must be linearly independent. Since $M$ has full rank, this could be ensured by permuting its columns, but as with rank deficiency, there’s in general no way to tell a priori what needs to be swapped. 
From the fact that the upper-right block of the product of the two matrices in (*) is zero, we can see that the right-hand columns of the inverse matrix are all elements of $\ker M$ and so in fact form a basis for the kernel. It would be interesting to know whether there’s some characteristic of chemical equations that ensures the above conditions, or the authors simply got lucky with their examples.
{"set_name": "stack_exchange", "score": 1, "question_id": 2155397}