The rank of an n × n matrix A is the maximum number of linearly independent columns in A. Column vectors of A, denoted ai, are linearly independent if the only set of scalars $\alpha_{i}$ such that
| $${\alpha}_{1}\mathbf{a^{1}}+{\alpha}_{2}\mathbf{a^{2}}+...+{\alpha}_{n}\mathbf{% a^{n}}=\mathbf{0}$$ | (23) |
is the set
| $${\alpha}_{1}={\alpha}_{2}=...={\alpha}_{n}=0$$ |
For a more concrete example, consider the following matrix.
| $$\mathbf{A}=\left(\begin{array}[]{cccc}0&1&1&2\\ 1&2&3&4\\ 2&0&2&0\end{array}\right)$$ |
The rank of A is two, since its third and fourth columns are linear combinations of its first two columns, i.e.
| $$\displaystyle\mathbf{{a}^{3}}\displaystyle=\mathbf{{a}^{1}+{a}^{2}}$$ $$\displaystyle\mathbf{{a}^{4}}\displaystyle=2\mathbf{{a}^{2}}$$ |
If A is an n × n matrix, it can be shown
| $$\operatorname{rank}\left(\mathbf{A}\right)\leq\min(m,n)$$ | (24) |
Furthermore,
| $$\operatorname{rank}\left(\mathbf{AB}\right)\leq\min(\operatorname{rank}\left(\mathbf{A}% \right),\operatorname{rank}\left(\mathbf{B}\right))$$ | (25) |
and
| $$\operatorname{rank}\left(\mathbf{A{A}^{T}}\right)=\operatorname{rank}\left(\mathbf{{A}^{T}A}\right)=\operatorname{rank}\left(\mathbf{A}\right)$$ | (26) |