# Row augmentation to solve for null-space vectors.

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"?

• It would be helpful if you included the relevant parts of the paper in the body of your question. External links can go stale. – amd Feb 24 '17 at 1:26
• I've edited my question to include the paper's summary of the procedure. – Tyberius Feb 24 '17 at 19:51
• The problem is that “e” doesn’t follow from “c” and “d” in general. Take for example the matrix $\pmatrix{1&0&0\\0&0&1}$. Its nullify is 1, but the augmented matrix is singular. The paper has some other flaws, such as not explaining what you should do if the result of MDTERM is less than the number of rows, in which case you won’t end up with a square matrix after augmenting. It would appear that the matrices involved have some some tacitly assumed properties that allow the described technique to work. – amd Feb 25 '17 at 0:57
• @amd Looking at the matrix you wrote, I realize there is at least one assumption for the matrices based on representing chemical reactions. A column couldn't be all zeros because that would imply from the start that this compound had no relationship with the reaction. My understanding is that if MDETERM (or the number of nonzero rows in the reduced row echelon form) is less than the number of rows, you would just get a larger nullity. I guess I might have to delve deeper into the references for the paper and see if the assumptions this null space method requires are described more rigorously. – Tyberius Feb 25 '17 at 16:49
• Use $\pmatrix{1&1&1\\0&0&1}$, then. The problem with both is that the columns are in the “wrong“ order for the augmentation to produce a nonsingular matrix. This is obvious for these two matrices, but not so obvious for something like $\pmatrix{2&2&2\\4&4&7}$. – amd Feb 26 '17 at 5:05

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.