A while ago I saw a paper in the <i>SIAM Review</i> - just one and a half pages of maths, followed by<p>"Remark 2. The theorem proved here gives a completely new general method. It generalizes all known results for balancing chemical equations cited chronologically in references [1]–[125]."
<a href="http://www.siam.org/journals/problems/downloadfiles/71-025s.pdf" rel="nofollow">http://www.siam.org/journals/problems/downloadfiles/71-025s....</a><p>Reference 125 is to this paper.
My high-school chemistry teacher had a tradition of announcing "Automatic A" challenges at the start of the term. One challenge was balancing a large chemical equation. I recall it required solving something like 6 equations with 6 unknowns. I solved it with multiple attempts and many pages of algebra, and crucial hints at sticking points from my dad who had a Masters in Chemistry. Easy A.<p>Another term, an A was promised for anyone turning in a "print out" of the numbers from 1 to 1 million. Dad, coming to the rescue again, got me access to a Microfilm printer at his work, and taught me just enough FORTRAN to generate the list. (Yeah, short program, all about the formatting.) Another easy A. The teacher's expression was priceless.
Amusingly, I discovered a method very similar to this in college. My method was simpler - stick a 1 in front of one chemical, then you get an n x n linear system of equations for the remaining compounds. Solve it, then figure out what to multiply by to get an int solution. I suspect that my version isn't stable, which I gather is the problem these guys are solving.<p>I was forbidden from using this method on the final, since it isn't the ad-hoc method that was taught.
I might be missing something big, but isn't chemical equation balancing just a system of linear Diophantine equations[1]? If it is, you should be able to solve it in O(n^3) time by converting to Smith normal form[2]. Unlike Hermite form, which the paper mentions, you don't need rational arithmetic or floating points.<p>[1]<a href="https://en.wikipedia.org/wiki/Diophantine_equation#System_of_linear_Diophantine_equations" rel="nofollow">https://en.wikipedia.org/wiki/Diophantine_equation#System_of...</a>
[2]<a href="https://en.wikipedia.org/wiki/Smith_normal_form" rel="nofollow">https://en.wikipedia.org/wiki/Smith_normal_form</a>
My face lit up when I found this paper after beginning balancing chemical equations in my 10th grade chemistry class this morning - so I thought I share it with HN.
I'd always assumed that stoichiometry problems could be solved with linear algebra, but was too lazy to investigate. Usually the problems assigned were easy enough that you didn't have to work too hard to figure them out.