# Gauss-Jordan elimination gives inconsistent matrix for a consistent system?

I am trying to get an analytical expression for a steady state of an ODE system governing a chemical reaction network via symbolic computer algebra systems. As an example for this question I'll take a fully connected chemical reaction network with three species $$N_0, N_1, N_2$$ and three bidirection reactions $$N_0 \rightleftarrows^{k_1}_{k_2} N_1 \rightleftarrows^{k_3}_{k_4} N_2 \rightleftarrows^{k_5}_{k_6} N_0$$ governed by ODEs $$\frac{dN_0}{dt} = -k_1N_0 -k_6N_0 + k_2N_1 + k_5N_2 \\ \frac{dN_1}{dt} = k_1N_0 -k_2N_1 - k_3N_1 + k_4N_2 \\ \frac{dN_2}{dt} = k_6N_0 +k_3N_1 - k_4N_2 - k_5N_2 \\$$ with mass constraint $$N_0 + N_1 + N_2 = N_T$$. From chemical reaction network theory I know that it can only have one equilibrium given $$N_T > 0$$. Alternatively, one can confirm that the rank of the matrix below is 3. However, deriving it analytically is a huge pain in the ass, therefore I was hoping to use symbolic algebra systems to solve this system of equations at equilibrium, namely: $$$$\begin{cases} 0 = -k_1N_0 -k_6N_0 + k_2N_1 + k_5N_2 \\ 0 = k_1N_0 -k_2N_1 - k_3N_1 + k_4N_2 \\ 0 = k_6N_0 +k_3N_1 - k_4N_2 - k_5N_2 \\ N_T = N_0 + N_1 + N_2 \end{cases}$$$$ which can be written as $$Ax=b$$ as follows: $$\left[\begin{array}{c, c, c} -k_1 - k_6 & k_2 & k_5 \\ k_1 & -k_2-k3 & k_4 \\ k_6 & k_3 & -k_4-k_5 \\ 1 & 1 & 1\\ \end{array}\right] \left[\begin{array}{c} N_0\\ N_1\\ N_2\\ \end{array}\right] = \left[\begin{array}{c} 0\\ 0\\ 0\\ N_T\\ \end{array}\right]$$ Now this can be solved algebraically by transforming it into a reduced row echelon form. However, a standard Gauss-Jordan elimination results in a matrix that says that the system is inconsistent, the extended matrix is: $$\left[\begin{array}{c, c, c, |c} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & N_T\\ \end{array}\right]$$ The working steps are omitted because there are a lot of them and they are lengthy. But the basic idea is that the last row simply gets eliminated and $$N_T$$ stays because all other elements are 0.

So, what is actually going on here? Is the basic Gauss-Jordan elimination (e.g. as given here) known to fail in such cases? Are there simple modifications to the algorithm that would take care of this? Any tips appreciated, if there are any questions/inaccuracies in my question please ask and I will try to clarify/expand.

• I don't know how you've done your Gauss Elimination, but it looks as if you've first operated on first three rows and got to $I$: that is certainly wrong as the first three rows are linearly dependent. But to answer this properly we need to know how you did the elimination. Commented Jan 7 at 15:23
• Why is operating on first three rows and getting $I$ wrong? Do you have a link to the Gauss-Jordan elimination that might be better than the one I provided? Because that one doesn't contain anything that would say that doing that is wrong. Commented Jan 7 at 15:27
• I think what Ancient Mathematician was saying is that if in transforming the first three rows to $I$ without in any step involving the fourth row then you must have made a mistake because that is impossible. However we can currently not know if that is what you did Commented Jan 7 at 15:30
• I did bog standard GE on the (trivial) case $k_0=k_1=\dots=k_5=1$ and the reduced form is $\begin{pmatrix} 1& 0 & 0 &N_T/3\\0& 1 & 0 &N_T/3\\0& 0 & 1 &N_T/3\\0& 0 & 0 & 0\end{pmatrix}$: no inconsistency and the expected solution with $N_0=N_1=N_2$. Commented Jan 7 at 17:23
• @linkz You are right that "the first three elements of that column are zero which negates any scaling and subtracting being done on the fourth row". But because the original third row is a combination of the first two rows you cannot reach the reduced form without swapping the original fourth row with modified (all-zeros) third row, and then the $N_T$ moves up into the top part. Just as it does in the example WmJagy challenges you with, as you'll see when you repair the arithmetic in your "solution". Commented Jan 8 at 7:44

No way of knowing what the computer is doing, especially as symbolic quantities are involved. Your first three rows sum to a zero row, meaning redundant (dependent). Drop the third row

$$\left[\begin{array}{c, c, c} -k_1 - k_6 & k_2 & k_5 \\ k_1 & -k_2-k_3 & k_4 \\ 1 & 1 & 1\\ \end{array}\right] \left[\begin{array}{c} N_0\\ N_1\\ N_2\\ \end{array}\right] = \left[\begin{array}{c} 0\\ 0\\ N_T\\ \end{array}\right]$$

This says that the N vector is any scalar multiple of the cross product of the first two rows. The particular scalar multiple is one that makes the sum to agree with $$N_T$$

For that matter, there is no particular difficulty finding the inverse of this 3 by 3 coefficient matrix.

• Oh yes, I know that the third row is a linear combination of the first two, but shouldn't Gauss Jordan be able to deal with the redundant row by itself, without having me remove it? It'd just be a row of zeros at the bottom. Commented Jan 7 at 16:20
• @linkz If you don't remove the 3rd row and do a proper Gauss eleimination then sure, the first three columns will be an $I$ sitting over a row of zeroes, but the final column will not be what you say since the fourth row will have been wound into the calculation at an earlier stage: it will be something like $(\alpha,\beta,\gamma,0) ^T$. Commented Jan 7 at 17:06
• @linkz please solve $$\left[\begin{array}{c, c, c} -7 & 4 & 5 \\ 1 & -8 & 9 \\ 6 & 4 & -14 \\ 1 & 1 & 1\\ \end{array}\right] \left[\begin{array}{c} N_0\\ N_1\\ N_2\\ \end{array}\right] = \left[\begin{array}{c} 0\\ 0\\ 0\\ 73\\ \end{array}\right]$$ if possible by hand. If I picked bad numbers replace with some pleasant ones Commented Jan 7 at 17:11

@Will Jagy, posting as answer because I want to show the steps, as outlined here. Here goes (apologies for any arithmetical mistakes)

$$\left[\begin{array}{c, c, c | c} -7 & 4 & 5 & 0\\ 1 & -8 & 9 & 0\\ 6 & 4 & -14 & 0\\ 1 & 1 & 1 & 73\\ \end{array}\right]$$ Scale row 1 by $$M_{1,1}$$ $$\left[\begin{array}{c, c, c | c} 1 & \frac{-4}{7} & \frac{-5}{7} & 0\\ 1 & -8 & 9 & 0\\ 6 & 4 & -14 & 0\\ 1 & 1 & 1 & 73\\ \end{array}\right]$$ Subtract row 1 * $$M_{n, 1}$$ for $$n = [2, 3, 4]$$ from row $$n$$ $$\left[\begin{array}{c, c, c | c} 1 & \frac{-4}{7} & \frac{-5}{7} & 0\\ 0 & \frac{-52}{7} & \frac{68}{7} & 0\\ 0 & \frac{44}{7} & \frac{-93}{7} & 0\\ 0 & \frac{11}{7} & \frac{12}{7} & 73\\ \end{array}\right]$$ Scale row 2 by $$M_{2,2}$$ $$\left[\begin{array}{c, c, c | c} 1 & \frac{-4}{7} & \frac{-5}{7} & 0\\ 0 & 1 & \frac{-68}{52} & 0\\ 0 & \frac{44}{7} & \frac{-93}{7} & 0\\ 0 & \frac{11}{7} & \frac{12}{7} & 73\\ \end{array}\right]$$ Subtract row 2 * $$M_{n, 2}$$ for $$n = [1, 3, 4]$$ from row $$n$$ $$\left[\begin{array}{c, c, c | c} 1 & 0 & \frac{-532}{364} & 0\\ 0 & 1 & \frac{-68}{52} & 0\\ 0 & 0 & \frac{-1844}{364} & 0\\ 0 & 0 & \frac{1372}{364} & 73\\ \end{array}\right]$$ Scale row 3 by $$M_{3,3}$$ $$\left[\begin{array}{c, c, c | c} 1 & 0 & \frac{-532}{364} & 0\\ 0 & 1 & \frac{-68}{52} & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & \frac{1372}{364} & 73\\ \end{array}\right]$$ Subtract row 3 * $$M_{n, 3}$$ for $$n = [1, 2, 4]$$ from row $$n$$ $$\left[\begin{array}{c, c, c | c} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 73\\ \end{array}\right]$$ and so the matrix is in reduced row echelon form with an inconsistent final row. Where is the mistake in this "algorithm"?

• thank you for posting this. I'll take a look Commented Jan 7 at 22:50
• Found the first mistake, and it's important: should have Subtract row 1 * $M_{n, 1}$ for $n = [2, 3, 4]$ from row $n$ $$\left[\begin{array}{c, c, c | c} 1 & \frac{-4}{7} & \frac{-5}{7} & 0\\ 0 & \frac{-52}{7} & \frac{68}{7} & 0\\ 0 & \frac{52}{7} & \frac{-68}{7} & 0\\ 0 & \frac{11}{7} & \frac{12}{7} & 73\\ \end{array}\right]$$ because you need to subtract six times the first row off the third Commented Jan 7 at 23:06
• On the same error: if you just subtract $1$ times the first row from the third, the resulting third row begins with a $5$ Commented Jan 8 at 2:43
• Ah, again, apologies about my arithemtic mistake, you are indeed correct! Also, your feedback and comments lead me to finding the error in the code that I was working with so I fixed that as well! Thank you! I marked your answer as correct to give you the credit you deserve. Commented Jan 8 at 11:07