Balance chemical equations without trial and error? In my AP chemistry class, I often have to balance chemical equations like the following:
$$ \mathrm{Al} + \text O_2 \to \mathrm{Al}_2 \mathrm O_3 $$
The goal is to make both side of the arrow have the same amount of atoms by adding compounds in the equation to each side.
A solution:
$$ 4 \mathrm{Al} + 3 \mathrm{ O_2} \to 2 \mathrm{Al}_2 \mathrm{ O_3} $$
When the subscripts become really large, or there are a lot of atoms involved, trial and error is impossible unless performed by a computer. What if some chemical equation can not be balanced?  (Do such equations exist?) I tried one for a long time only to realize the problem was wrong.
My teacher said trial and error is the only way. Are there other methods?

To solve this problem, create an ordered set of chemical elements $(Al,O)$ and an ordered set of chemical species $(Al,Al_2O_3,O_2)$.
The ordering of the chemical elements can be used to create a vector for each chemical species.
$Al = \begin{pmatrix}1\\0\end{pmatrix}$
$Al_2O_3 = \begin{pmatrix}2\\3\end{pmatrix}$
$O_2 = \begin{pmatrix}0\\2\end{pmatrix}$
The ordering of the chemical species (this ordering is arbitrary, but standard linear algebra algorithms will produce different results) can be used to create an element abundance matrix, $A$.
$A = \begin{pmatrix}1&2&0\\0&3&2\end{pmatrix}$
The coefficients of the set of linearly independent stoichiometric equations can be represented by the stoichiometric matrix, $N$, where $N$ is a representation of the null space of $A$.
$AN=0$
To put the stoichiometric matrix into 'canonical form' apply the operations:
$(RREF(N^T))^T$
The ordering of the species will preferentially make the stoichiometric coefficents of the species at the left side of matrix $A$ to have coefficents of $1$. This method will produce the maximal number of linearly independent stoichiometric equations. They can be added or multiplied and still represent a stoichiometric equation (they are linearly independent).
If you are going to try and calculate thermodynamic equilibrium with a mixture of gas and condensed species, I recommend ordering the gas species first in the list. This will try and isolate 1 gas per independent stoichiometric equation (if possible) and will facilite using the chemical equilibrium constant method $K_{eq}$ to calculate thermodynamic equilibrium.
