Chiò’s Method

When doing Gauss’s Method on a matrix that contains only integers people often like to keep it that way. To avoid fractions in the reduction of this matrix

$$A=\left(\begin{array}{ccc}2& 1& 1\\ 3& 4& -1\\ 1& 5& 1\end{array}\right)$$

they may start by multiplying the lower rows by $2$

$$\begin{array}{cc}\underset{\begin{array}{l}2{\rho }_3\end{array}}{\overset{2{\rho }_2\phantom{(}}{⟶}}\left(\begin{array}{ccc}2& 1& 1\\ 6& 8& -2\\ 2& 10& 2\end{array}\right)& \text{(}\ast \text{)}\end{array}$$

so that elimination in the first column goes like this.

$$\begin{array}{cc}\underset{\begin{array}{l}-{\rho }_1+{\rho }_3\end{array}}{\overset{-3{\rho }_1+{\rho }_2\phantom{(}}{⟶}}\left(\begin{array}{ccc}2& 1& 1\\ 0& 5& -5\\ 0& 8& 0\end{array}\right)& \text{(}\ast \ast \text{)}\end{array}$$

This all-integer approach is easier for mental calculations. And, using integer arithmetic on a computer avoids some sticky issues involving floating point calculations [Kahan]. So there are sound reasons for this approach.

Another advantage of this approach is that we can easily apply Laplace’s expansion to the first column of ($\ast \ast$) and then get the determinant by remembering to divide by $4$ because of ($\ast$).

Here is the general $3\times 3$ case of this approach to finding the determinant. First, assuming $a_{1,1}\ne 0$, we can rescale the lower rows.

$$A=\left(\begin{array}{ccc}{a}_{1,1}& a_{1,2}& a_{1,3}\\ a_{2,1}& a_{2,2}& a_{2,3}\\ a_{3,1}& a_{3,2}& a_{3,3}\end{array}\right)\underset{\begin{array}{l}{a}_{1,1}{\rho }_3\end{array}}{\overset{a_{1,1}{\rho }_2\phantom{(}}{⟶}}\left(\begin{array}{ccc}{a}_{1,1}& a_{1,2}& a_{1,3}\\ a_{2,1}{a}_{1,1}& a_{2,2}{a}_{1,1}& a_{2,3}{a}_{1,1}\\ a_{3,1}{a}_{1,1}& a_{3,2}{a}_{1,1}& a_{3,3}{a}_{1,1}\end{array}\right)$$

This rescales the determinant by $a_{1,1}^2$. Now eliminate down the first column.

$$\underset{\begin{array}{l}-a_{3,1}{\rho }_1+{\rho }_3\end{array}}{\overset{-a_{2,1}{\rho }_1+{\rho }_2\phantom{(}}{⟶}}\left(\begin{array}{ccc}{a}_{1,1}& a_{1,2}& a_{1,3}\\ 0& a_{2,2}{a}_{1,1}-a_{2,1}{a}_{1,2}& a_{2,3}{a}_{1,1}-a_{2,1}{a}_{1,3}\\ 0& a_{3,2}{a}_{1,1}-a_{3,1}{a}_{1,2}& a_{3,3}{a}_{1,1}-a_{3,1}{a}_{1,3}\end{array}\right)$$

Let $C$ be the $1,1$ minor. By Laplace the determinant of the above matrix is $a_{1,1}det(C)$. We thus have $a_{1,1}^{2}det(A)=a_{1,1}det(C)$ and since $a_{1,1}\ne 0$ this gives $det(A)=det(C)/a_{1,1}$.

To do larger matrices we must see how to compute the minor’s entries. The pattern above is that each element of the minor is a $2\times 2$ determinant. For instance, the entry in the minor’s upper left $a_{2,2}{a}_{1,1}-a_{2,1}{a}_{1,2}$, which is the $2,2$ entry in the above matrix, is the determinant of the matrix of these four elements of $A$.

$$\left(\begin{array}{ccc}{\displaystyle a_{1,1}}& {\displaystyle a_{1,2}}& a_{1,3}\\ {\displaystyle a_{2,1}}& {\displaystyle a_{2,2}}& a_{2,3}\\ a_{3,1}& a_{3,2}& a_{3,3}\end{array}\right)$$

And the minor’s lower left, the $3,2$ entry from above, is the determinant of the matrix of these four.

$$\left(\begin{array}{ccc}{\displaystyle a_{1,1}}& {\displaystyle a_{1,2}}& a_{1,3}\\ a_{2,1}& a_{2,2}& a_{2,3}\\ {\displaystyle a_{3,1}}& {\displaystyle a_{3,2}}& a_{3,3}\end{array}\right)$$

So, where $A$ is $n\times n$ for $n\ge 3$, we let Chiò’s matrix $C$ be the $(n-1)\times (n-1)$ matrix whose $i,j$ entry is the determinant

$$\left|\begin{array}{cc}{a}_{1,1}& a_{1,j+1}\\ a_{i+1,1}& a_{i+1,j+1}\end{array}\right|$$

where $1<i,j\le n$. Chiò’s method for finding the determinant of $A$ is that if $a_{1,1}\ne 0$ then $det(A)=det(C)/a_{1,1}^{n-2}$. (By the way, nothing in Chiò’s formula requires that the numbers be integers; it applies to reals as well.)

To illustrate we find the determinant of this $3\times 3$ matrix.

$$A=\left(\begin{array}{ccc}2& 1& 1\\ 3& 4& -1\\ 1& 5& 1\end{array}\right)$$

This is Chiò’s matrix.

$$C=\left(\begin{array}{cc}\left|\begin{array}{cc}2& 1\\ 3& 4\end{array}\right|& \left|\begin{array}{cc}2& 1\\ 3& -1\end{array}\right|\\ \left|\begin{array}{cc}2& 1\\ 1& 5\end{array}\right|& \left|\begin{array}{cc}2& 1\\ 1& 1\end{array}\right|\end{array}\right)=\left(\begin{array}{cc}5& -5\\ 9& 1\end{array}\right)$$

The formula for $3\times 3$ matrices $det(A)=det(C)/a_{1,1}$ gives $det(A)=(50/2)=25$.

For a larger determinant we must do multiple steps but each involves only $2\times 2$ determinants. So we can often calculate the determinant just by writing down a bit of intermediate information. For instance, with this $4\times 4$ matrix

$$A=\left(\begin{array}{cccc}3& 0& 1& 1\\ 1& 2& 0& 1\\ 2& -1& 0& 3\\ 1& 0& 0& 1\end{array}\right)$$

we can mentally doing each of the $2\times 2$ calculations and only write down the $3\times 3$ result.

$$C_3=\left(\begin{array}{ccc}\left|\begin{array}{cc}3& 0\\ 1& 2\end{array}\right|& \left|\begin{array}{cc}3& 1\\ 1& 0\end{array}\right|& \left|\begin{array}{cc}3& 1\\ 1& 1\end{array}\right|\\ \left|\begin{array}{cc}3& 0\\ 2& -1\end{array}\right|& \left|\begin{array}{cc}3& 1\\ 2& 0\end{array}\right|& \left|\begin{array}{cc}3& 1\\ 2& 3\end{array}\right|\\ \left|\begin{array}{cc}3& 0\\ 1& 0\end{array}\right|& \left|\begin{array}{cc}3& 1\\ 1& 0\end{array}\right|& \left|\begin{array}{cc}3& 1\\ 1& 1\end{array}\right|\end{array}\right)=\left(\begin{array}{ccc}6& -1& 2\\ -3& -2& 7\\ 0& -1& 2\end{array}\right)$$

Note that the determinant of this is $a_{1,1}^{4-2}=3^2$ times the determinant of $A$.

To finish, iterate. Here is Chiò’s matrix of $C_3$.

$$C_2=\left(\begin{array}{cc}\left|\begin{array}{cc}6& -1\\ -3& -2\end{array}\right|& \left|\begin{array}{cc}6& 2\\ -3& 7\end{array}\right|\\ \left|\begin{array}{cc}6& -1\\ 0& -1\end{array}\right|& \left|\begin{array}{cc}6& 2\\ 0& 2\end{array}\right|\end{array}\right)=\left(\begin{array}{cc}-15& 48\\ -6& 12\end{array}\right)$$

The determinant of this matrix is $6$ times the determinant of $C_3$. The determinant of $C_2$ is $108$. So $det(A)=108/(3^2\cdot 6)=2$.

Laplace’s expansion formula reduces the calculation of an $n\times n$ determinant to the evaluation of a number of $(n-1)\times (n-1)$ ones. Chiò’s formula is also recursive but it reduces an $n\times n$ determinant to a single $(n-1)\times (n-1)$ determinant, calculated from a number of $2\times 2$ determinants. However, for large matrices Gauss’s Method is better than either of these; for instance, it takes roughly half as many operations as Chiò’s Method [Fuller & Logan].

Computer Code

This implements Chiò’s Method. It is in the computer language Python.

#!/usr/bin/python
# chio.py
#  Calculate a determinant using Chio's method.
# Jim Hefferon; Public Domain
# For demonstration only; for instance, does not handle the M[0][0]=0 case

def det_two(a,b,c,d):
    """Return the determinant of the 2x2 matrix [[a,b], [c,d]]"""
    return a*d-b*c

def chio_mat(M):
    """Return the Chio matrix as a list of the rows
        M  nxn matrix, list of rows"""
    dim=len(M)
    C=[]
    for row in range(1,dim):
        C.append([])
        for col in range(1,dim):  
            C[-1].append(det_two(M[0][0], M[0][col], M[row][0], M[row][col]))
    return C

def chio_det(M,show=None):
    """Find the determinant of M by Chio's method
        M  mxm matrix, list of rows"""
    dim=len(M)
    key_elet=M[0][0]
    if dim==1:
        return key_elet
    return chio_det(chio_mat(M))/(key_elet**(dim-2))


if __name__=='__main__':
    M=[[2,1,1], [3,4,-1], [1,5,1]]
    print "M=",M
    print "Det is", chio_det(M)

This is the result of calling the program from a command line.

$ python chio.py
M=[[2, 1, 1], [3, 4, -1], [1, 5, 1]]
Det is 25

References cited in this section