Given an unbalanced chemical equation, is it possible to determine the largest possible coefficient that could be used in the balanced equation?
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.