Given an unbalanced chemical equation, is it possible to determine the largest possible coefficient that could be used in the balanced equation? I am writing a program to balance chemical equations, and would love to know if there is an algebraic way to determine the greatest possible coefficient that I would need to check.
In short

Just use matrices.

In long

Consider this equation to be balanced:

$$\ce{CuSCN + KIO3 + HCl -&gt; CuSO4 + KCl + HCN + ICl + H2O}$$

(source with spoiler)

We are trying to solve this equation:

$$\ce{aCuSCN + bKIO3 + cHCl -&gt; dCuSO4 + eKCl + fHCN + gICl + hH2O}$$

Now, we move every term to the left hand side (warning: handwavey chemistry):

$$\ce{aCuSCN + bKIO3 + cHCl - dCuSO4 - eKCl - fHCN - gICl - hH2O = 0}$$

Transform into matrix form (the element names are just for reference):

$$
\begin{matrix}
\ce{Cu}\\
\ce{S}\\
\ce{C}\\
\ce{N}\\
\ce{K}\\
\ce{I}\\
\ce{O}\\
\ce{H}\\
\ce{Cl}
\end{matrix}
\left(
\begin{matrix}
1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 &amp;0 \\
1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 &amp;0 \\
1 &amp;0 &amp;0 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 \\
1 &amp;0 &amp;0 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 \\
0 &amp;1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 \\
0 &amp;1 &amp;0 &amp;0 &amp;0 &amp;0 &amp;-1&amp;0 \\
0 &amp;3 &amp;0 &amp;-4&amp;0 &amp;0 &amp;0 &amp;-1\\
0 &amp;0 &amp;1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;-2\\
0 &amp;0 &amp;1 &amp;0 &amp;-1&amp;0 &amp;-1&amp;0
\end{matrix}
\right)
\left(
\begin{matrix}
a\\
b\\
c\\
d\\
e\\
f\\
g\\
h
\end{matrix}
\right)
=
\left(
\begin{matrix}
0\\0\\0\\0\\0\\0\\0\\0\\0\\
\end{matrix}
\right)
$$

Notice that the biggest matrix is not a square. You must transform it to a square. If the elements are in excess (just like this case), add variables; otherwise, add elements. Set the extra variables/elements to zero:

$$
\begin{matrix}
\ce{Cu}\\
\ce{S}\\
\ce{C}\\
\ce{N}\\
\ce{K}\\
\ce{I}\\
\ce{O}\\
\ce{H}\\
\ce{Cl}
\end{matrix}
\left(
\begin{matrix}
1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 &amp;0 &amp;0 \\
1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 &amp;0 &amp;0 \\
1 &amp;0 &amp;0 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 \\
1 &amp;0 &amp;0 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 \\
0 &amp;1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 &amp;0 &amp;0 \\
0 &amp;1 &amp;0 &amp;0 &amp;0 &amp;0 &amp;-1&amp;0 &amp;0 \\
0 &amp;3 &amp;0 &amp;-4&amp;0 &amp;0 &amp;0 &amp;-1&amp;0 \\
0 &amp;0 &amp;1 &amp;0 &amp;0 &amp;-1&amp;0 &amp;-2&amp;0 \\
0 &amp;0 &amp;1 &amp;0 &amp;-1&amp;0 &amp;-1&amp;0 &amp;0
\end{matrix}
\right)
\left(
\begin{matrix}
a\\
b\\
c\\
d\\
e\\
f\\
g\\
h\\
i
\end{matrix}
\right)
=
\left(
\begin{matrix}
0\\0\\0\\0\\0\\0\\0\\0\\0\\
\end{matrix}
\right)
$$

Note: $i$ must be zero.

Now you can use any algorithm for solving homogeneous square matrix equations to continue.