Determinants and Simultaneous Linear Equations

Definition 1: The determinant, det A, also denoted |A|, of an n × n square matrix A is defined recursively as follows:

If A is a 1 × 1 matrix [a] (i.e. a scalar) then det A = a. Otherwise,

Determinant formula

where Aij is matrix A with row i and column j removed.

Note that if A = \left[ \! \begin{array}{cc} 3 & 5 \\4 & 0 \end{array} \! \right], then we use the notation \left| \!\begin{array}{cc} 3 & 5 \\4 & 0 \end{array} \!\right| for det A.

Excel Functions: Excel provides the following function for calculating the determinant of a square matrix:

MDETERM(A): If A is a square array, then MDETERM(A) = det A. This is not an array function.

The supplemental function DET(A) provides equivalent functionality.

Property 1:

  1. det AT = det A
  2. If A is a diagonal matrix, then det A = the product of the elements on the main diagonal of A

Proof: Both of these properties are a simple consequence of Definition 1

Property 2: \left| \!\begin{array}{cc} a & b \\c & d \end{array} \!\right|ad  – bc

Example 1: Calculate det A where

image2933

From Definition 1 and Property 2 it follows that

image2934

Of course we can get the same answer by using Excel’s function MDETERM(A).

Property 3: If A and B are square matrices of the same size then det AB = det A ∙ det B

Property 4: A square matrix A is invertible if and only if det A ≠ 0. If A is invertible then

Determinant inverse matrix

The first assertion is equivalent to saying that a square matrix A is singular if and only if det A = 0.

Property 5: Rules for evaluating determinants:

  1. The determinant of a triangular matrix is the product of the entries on the diagonal.
  2. If we interchange two rows, the determinant of the new matrix is the negative of the old one.
  3. If we multiply one row by a constant, the determinant of the new matrix is the determinant of the old one multiplied by the constant.
  4. If we add one row to another one multiplied by a constant, the determinant of the new matrix is the same as the old one.

Observation: The rules in Property 5 are sufficient to calculate the determinant of any square matrix. The idea is to transform the original matrix into a triangular matrix and then use rule 1 to calculate the value of the determinant.

We now present an algorithm based on Property 5 for calculating det A, where A = [aij] is an n ×  matrix. Start by setting the value of the determinant to 1, and then perform steps 1 to n as follows.

Step k – part 1(a): If akk ≠ 0, multiply the current value of the determinant by akk and then divide all the entries in row k by akk (rule 3 of Property 5).

Step k – part 1(b): If akk = 0, exchange row k with any row  below it (i.e. k < m ≤ n) for which amk ≠ 0, multiply the current value of the determinant by -1 (rule 2) and then perform step 1(a) above. If no such row exists then terminate the algorithm and return the value of 0 for the determinant.

Step k – part 2: For every row m below row k, add –amk times row k to row m (rule 4). This guarantees that aij = 0 for all i > k and jk.

After the completion of step n, we will have a triangular matrix whose diagonal contains all 1s, and so by rule 1, the determinant is equal to the current value of the determinant.

Example 2: Using Property 5, find

image2949

We present the steps looking from left to right and then top to bottom in Figure 1. For each step the rule used is specified as well as the multiplier of the determinant calculated up to that point.

Determinant Gaussian Elimination Excel

Figure 1 – Calculating the determinant in Example 2

This shows that the determinant is -5, the same answer given when using Excel’s MDETERM function.

Observation: In step – part 1(b) of the above procedure we exchange two rows if akk = 0. Given that we need to deal with round off errors, what happens if akk is small but not quite zero? In order to reduce the impact of round off errors, we should modify step k – part 1 as follows:

Step k – part 1: Find m ≥ such that the absolute value of amk is largest. If this amk ≈ 0 (i.e. |amk|< ϵ where ϵ is some predefined small value) then terminate the procedure. If m > k then exchange rows m and k.

Definition 2: A set of n linear equations

Simultaneous linear equations

in k unknowns xj can be viewed as the matrix equation AX = C where A is the n × k matrix [aij], X is the k × 1 column vector [xj] and C is the n × 1 column vector [cj].

Property 6: If A is a square matrix (i.e. the number of equations is equal to the number of unknowns), the equation AX = C has a unique solution if and only if A is invertible (i.e. det A ≠ 0), and in this case the unique solution is given by X = A-1 C.

Property 7 (Cramer’s Rule): If the square matrix  is invertible, the unique solution to  is given by

Cramers rule formula

where Aj is A with the jth column replaced by the entries of C.

Example 3: Solve the following linear system using Cramer’s Rule:

image2968

In Figure 2, we calculate det A and det Aj for each j.

Cramers rule determinant

Figure 2 – Calculating a determinant using Cramer’s rule

It now follows that x = -6/9 = -2/3, y = 3/9 = 1/3 and z = 0/9 = 0.

Per Property 6, we can get the same result by calculating A-1 C, which can be carried out in Excel using the formula =MMULT(MINVERSE(A), C). For Example 3, this yields

image2975

Definition 3: When C from Definition 2 is not the null matrix, then the linear equations are called heterogeneous. When C = Ο the linear equations are called homogeneous. In this case Ο is a solution of AX = Ο, called the trivial solution.

Property 8: If A is invertible then X = Ο is the only solution of AX = Ο.

Proof: This follows from Property 6.

Observation: When A is not invertible (i.e. det A = 0) any scalar multiple of a non-trivial solution to the homogeneous equation AX = Ο is also a solution. To find such a solution we can use the Gaussian Elimination method, a method which is similar to the one we used to calculate the determinant of a square matrix based on Property 5. This approach works for any A (whether square or not, and whether invertible or not).

Definition 4: If A is an n × k matrix and B is an n × m matrix then the augmented matrix A|B is an n × (k+m) matrix whose first  columns are identical to the columns in A and whose remaining  columns are identical to the columns in B.

Property 9: If A′ and C′ are derived from A and C based on any one of the following transformations, then the equations AX = C and AX = C have the same solutions.

  1. Interchange of any two rows
  2. Multiplication of any row by a constant
  3. Addition of any row multiplied by a constant to another row

Observation: Typically we apply the above transformations to the augmented matrix A|C.

Definition 5: The Gaussian Elimination Method is a way of solving linear equations and is based on the transformations described in Property 9. Suppose A and C are as described in Definition 2.

         Step 0 – set i = 1 and j = 1

We now apply the following series of transformation to the augmented matrix  (step 1 through step p where p is the smaller of n and k):

Step i – part 1: Find r i such that the absolute value of arj is largest. If arj ≈ 0 (i.e. |arj| < ϵ where ϵ is some predefined small value), then if j = n terminate the procedure; otherwise replace j by j + 1 and repeat step i. If not arj ≈ 0 and r > k then exchange rows r and i (rule 1).

Step i – part 2: Divide all the entries in row i by aij (rule 2).

Step i – part 3: For every row r below row i, add –arj times row i to row r (rule 3). This guarantees that arc = 0 for all r > i and cj.

Observation: For non-homogeneous equations (i.e. ≠ Ο) there are three possibilities: there are an infinite number of solutions, there are no solutions or there is a unique solution. For homogeneous equations (i.e. C = Ο) there are two possibilities: there are an infinite number of solutions or there is a unique solution, namely the trivial solution where X = Ο.

Example 4: Solve the following linear system using Gaussian Elimination:

image3000

Figure 3 displays the steps in the Gaussian Elimination process for Example 4.

Gaussian elimination Excel

Figure 3 – Solving linear equations using Gaussian elimination

Since A transforms into the identity matrix we know that the transform of C is the unique solution to the system of linear equations, namely x = 0, y = 2 and z = -1. Note that we get the same result by calculating X = A-1 C.

Example 5: Solve the following homogeneous linear system using Gaussian Elimination:

image3002

By Gaussian Elimination from Figure 4 we see that the only solution is the trivial solution:

Homogeneous equations Gaussian elimination

Figure 4 – Solving homogeneous linear equations via Gaussian elimination

Example 6: Solve the following homogeneous linear system using Gaussian Elimination:

image3005

This time Gaussian Elimination produces a row with all zeros (see Figure 5), and the number of non-zero rows = 2 < 3 unknowns. Thus there are an infinite number of solutions.

Homogeneous linear equations Gaussian

Figure 5 – Finding solutions to homogeneous linear equations

The solutions can take the form x = -2.5t, y = .5t, z = t for any value of t.

Observation: As we can see from the above examples, a homogeneous equation AX = O, where A is an m × n matrix, has a unique solution when there are n non-zero rows after performing Gaussian Elimination. Otherwise the equation has an infinite number of solutions.

Real Statistics Excel Functions: We provide the following supplemental Excel array function for carrying out the Gaussian Elimination procedure.

ELIM(R1, prec): an array function which outputs the results of Gaussian Elimination on the augmented matrix found in the array R1. The shape of the output is the same as the shape of R1.

LINEQU(R1, prec): an array function which returns an n × 1 column vector with the unique solution to equations defined by the augmented m × (n+1) matrix found in array R1; returns a vector consisting of #N/A! if there is no solution and a vector consisting of #NUM! if there are an infinite number of solutions.

By default, each of these functions assumes that an entry with absolute value less than 0.0001 is equivalent to zero. This is necessary since small values are not treated as zero in the Gaussian elimination algorithm described above. You can change this default value to something else by inserting a second parameter in either of these functions: e.g. ELIM(R1, prec) or LINEQU(R1, prec). Thus ELIM(R1) = ELIM(R1, 0.0001).

Real Statistics Data Analysis Tool: The Solve Set of Linear Equations data analysis tool contained in the Real Statistics Resource Pack provides equivalent functionality to LINEQU and ELIM. To use this tool, enter Ctrl-m and select Solve Set of Linear Equations from the menu. When a dialog box appears, fill in the Input Range (with the same range as R1 above). Selecting Show solution only is equivalent to LINEQU(R1), while not clicking on this option is equivalent to ELIM(R1).

Observation: Gaussian Elimination can also be used to invert a square n × n matrix A by applying the above procedure to A|In. If the procedure terminates before n steps have been completed then A is not invertible. If the procedure terminates after n steps (in which case A′ = In) then C′ = A-1.

Example 7: Use Gaussian Elimination to invert the matrix

image3014

The result is shown in Figure 6.

Matrix inversion Gaussian elimination

Figure 6 – Inverting a matrix using Gaussian elimination

The fact that A transforms into the identity matrix indicates that A is invertible. The inverse is given by the transformation of the identity matrix, namely

image3016

This is the same result as using the Excel formula MINVERSE(A).

5 Responses to Determinants and Simultaneous Linear Equations

  1. Ireej says:

    Great blog! Do you have any tips for aspiring writers?
    I’m hoping to start my own website soon but I’m a little lost on everything.
    Would you advise starting with a free platform like WordPress or go for a paid option? There are so many
    options out there that I’m completely overwhelmed .. Any ideas?
    Thanks a lot!

    • Charles says:

      Ireej,
      To gain some experience I started by putting the website up on the free WordPress platform. It worked for a while until I found that I needed some of the tools that are not available on the free platform.
      Charles

  2. Eugene says:

    As a side note – if we accept “Definition 1” then “Property 2” should be read as $\begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad – bc$.
    Not “ac – bd”.

  3. Allamah Ali Mele says:

    Really this site have help me a lot and i am really appreciate the efforts of all those who contributed to development of this site. I am looking forward to send me more problems and solutions on determinant and matrices to my email address to enable me study at home because, presently i am student.

Leave a Reply

Your email address will not be published. Required fields are marked *