## Linear Systems of Equations: Linear Algebra

### Definitions

#### Linear Vector Spaces

In this course, by a linear vector space we mean the set

The dimension of this vector space is . A vector in this space has components each of which is a real number. The zero vector is the vector whose components are all equal to zero.

For example is the two-dimensional linear vector space. Each vector in this space has two components. can be represented geometrically by a plane. is a three-dimensional linear vector space. Each vector in this space has three components. The vector is the zero vector in . The vector is the zero vector in .

#### Linear Functions between Vector Spaces(Matrices)

Given a linear vector space , and another linear vector space , a linear function has the following form, :

The function takes a vector with components and returns a vector which has components. Using matrix notation, the above can be written in the following more convenient form:

If we denote the matrix of numbers by , then the linear function can be written in the following simple form:

We noted that is an element of the linear vector space . Similarly, we view as an element of the possible linear functions from to which is denoted:

If , then for simplicity, we say that . We also use the symbol to denote the set of square matrices that live in the space .

For a visual representation showing the action of the matrix on the space , see the tool shown here.

##### Matrix Transpose

If , then the transpose of , namely is defined as the matrix whose columns are the rows of .

#### Examples

##### Example 1

Consider the function defined as . Following the above definition, is a one-dimensional vector and the matrix has dimensions . In this case and .

##### Example 2

Consider the function defined as follows: :

In matrix form, this function can be represented as follows:

This function takes vectors that have three components and gives vectors that have two components. The matrix associated with this linear function has dimensions , lives in the space , and has the form:

In this case, is simply:

##### Example 3

Consider the function defined as follows: :

In matrix form, this function can be represented as follows:

This function takes vectors that have three components and gives vectors that have three components. The matrix associated with this linear function has dimensions , lives in the space , and has the form:

In this case, is simply:

##### Example 4

Consider the function defined as follows: :

In matrix form, this function can be represented as follows:

This function takes vectors that have three components and gives vectors that have one component. The matrix associated with this linear function has dimensions , lives in the space , and has the form:

In this case, is simply:

#### Linear System of Equations

Let and given a vector , a linear system of equations seeks the solution to the equation:

In a matrix component form the above equation is:

Another way of viewing this set of equations is as follows:

The solution for a linear system of equations is the numerical value for the variables that would satisfy the above equations. There are three possible scenarios:

##### Scenario 1

If then we have more unknown components of the -dimensional vector than we have equations. The system is then termed underdetermined. This results in having many possible solutions, or no solution. For example, consider the linear system of equations defined as:

There are many possible solutions that would satisfy the above equation. One solution can be obtained by setting . Then:

which results in and . Therefore one possible solution is:

Another possible solution can be obtained by setting . Then:

which results in and . Therefore another possible solution is:

In fact, there are infinite possible solutions that depend on what value you choose for . So, if is set such that , then we have:

Therefore:

and

Therefore:

##### Scenario 2

If and the equations are linearly independent, then we have more equations than we have unknown components of the -dimensional vector . This results in having too many restrictions which prevents us from finding a solution. In this case, the system is termed overdetermined. For example, consider the linear system of equations defined as:

In this system, we have three independent equations and two unknowns and . If the first two equations are used to find a solution, then the third equation will present a contradiction. The first two equations have the following form:

which result in the solution , and . If we substitute this solution into equation 3 we get:

##### Scenario 3

If and the equations are independent, i.e., the rows of the matrix are linearly independent, then one unique solution exists and the matrix that forms the equation has an inverse. In this case, there exists a matrix such that:

To know whether the equations are independent or not the determinant function defined below is sufficient. If the determinant of a matrix is equal to 0, then the rows of the matrix are linearly dependent, and so, an inverse cannot be found. If the determinant of a matrix on the other hand is not equal to 0, then the rows of the matrix are linearly independent and an inverse can be found.

For example, consider the system defined as:

The rows of the matrix are clearly linearly independent. The inverse of can be found (which will be discussed later in more detail). For now, we can simply solve the two equations as follows. From the second equation we get:

Substituting into the first equation we get:

Therefore, the system has a unique solution.

If and the equations are dependent, i.e., the rows of the matrix are linearly dependent, then it is not possible to find a unique solution for the linear system of equations. For example, consider the system defined as:

The rows of the matrix are clearly linearly dependent. The inverse of can not be found (which will be discussed later in more detail). The system presents a contradiction and cannot be solved because the first equation predicts that while the second equation predicts that !

As a different example, consider the system defined as:

The rows of the matrix are clearly linearly dependent. The inverse of can not be found (which will be discussed later in more detail). The system has infinite number of possible solutions. The first and second equations give us the relationship . So, by assuming any value for , we can find a value for . For example, if , then . Another possible solution is and .

We will focus in the remaining part of this section on how to find a solution for a linear system of equations when .

### Special Types of Square Matrices

#### Symmetric Matrix

A symmetric matrix is a matrix that satisfies . For example:

is a symmetric matrix.

#### Identity Matrix

The identity matrix is the matrix whose diagonal components have the value of 1 while its off diagonal components have a value of zero. For example, has the form:

This is called the identity matrix because it takes every vector and returns the same vector. For example, consider the general vector with components , , and . The same vector is obtained after the operation :

#### Diagonal Matrix

A matrix is called diagonal if all its off diagonal components are zero. The identity matrix is a diagonal matrix. Similarly, the following matrix is diagonal:

#### Upper Triangular Matrix

Let . is an upper triangular matrix if all the components below the diagonal components are equal to zero. For example, the following matrix is an upper triangular matrix:

#### Lower Triangular Matrix

Let . is a lower triangular matrix if all the components above the diagonal components are equal to zero. For example, the following matrix is a lower triangular matrix:

#### Banded Matrix

A matrix is called banded if all its components are zero except the components on the main diagonal and one or more diagonals on either side. To quantify *how banded* a matrix is, the bandwidth of a matrix is defined. The bandwidth of a matrix indicates the width of the element band out of which all other elements are zero. To define the bandwidth, first we define the lower or left half-bandwidth, and the upper or right half-bandwidth as follows.

The upper bandwidth is the smallest positive integer such that when . This finds the last diagonal, above the main diagonal, that contains non-zero elements.

The lower bandwidth is the smallest positive integer such that when . This finds the last diagonal, below the main diagonal, that contains non-zero elements.

The bandwidth of can be defined as: .

Note that the bandwidth may have different definition, e.g. maximum of and , in some text.

Examples:

is banded with a bandwidth of .

is banded with a bandwidth of .

The bandwidth of a diagonal matrix is

An upper triangular matrix is not a banded matrix, but the definition of the bandwidth leads to a bandwidth of for this matrix.

### Matrix Operations

#### Matrix Addition

Let . Consider the function and the function . Then, the function is given as:

where is computed by adding each component in to the corresponding component in . For example, consider the two matrices:

Then, the matrix can be computed as follows:

Two matrices can only be added if they have the same dimensions.

#### Matrix Multiplication

Consider the matrix which takes vectors of dimensions and returns vectors of dimensions . The matrix has dimensions . Consider the matrix which takes vectors of dimension and gives vectors of dimension . The matrix has dimensions . The combined operation takes vectors of dimensions and gives vectors of dimension . This matrix corresponding to the combined operation can be obtained by taking the dot product of the row vectors of the matrix with the column vectors of the matrix . This can only be done if the inner dimensions are equal to each other. The product would have dimensions of and it is such that :

For example, consider the two matrices:

We can only perform the operation but the opposite is not defined. The matrix multiplication results in:

You can use “.” in Mathematica to multiply matrices, or you can use “MMULT” in excel to multiply matrices.

View Mathematica CodeNn = {{1, 4}, {2, 2}, {3, 5}}; M = {{2, 3, 1, 5}, {0, -1, 2, 4}}; L = Nn.M; L // MatrixForm

import numpy as np Nn = [[1, 4], [2, 2], [3, 5]] M = [[2, 3, 1, 5], [0, -1, 2, 4]] np.matmul(Nn,M)

It is important to note that when the dimensions are appropriate, then matrix multiplication is associative and distributive, i.e., given the three matrices then:

However, matrix multiplication is not necessarily commutative, i.e., . For example, consider the matrices

Then:

#### Matrix Determinant

If such that:

then . If such that:

then .

Let . The matrix determinant can be defined using the recursive relationship:

where and is formed by eliminating the 1st row and column of the matrix . It can be shown that the rows of are linearly dependent. In other words, if and only if the matrix cannot be inverted. The function “Det[]” in Mathematica can be used to calculate the determinant of a matrix. In Excel, you can use the function “MDETERM()” to calculate the determinant of a matrix as well.

The following function in Mathematica computes the determinant of the matrix using the above recursive relationship and then compares the solution with the built-in function “Det[]” in Mathematica.

View Mathematica Codefdet[M_] := (n = Length[M]; If[n == 2, (M[[1, 1]]*M[[2, 2]] - M[[1, 2]]*M[[2, 1]]),Sum[(-1)^(i + 1) M[[1, i]]*fdet[Drop[M, 1, {i}]], {i, 1, n}]]); M = {{1, 1, 3, 7}, {4, 4, 5, 0}, {1, 5, 5, 6}, {1, -4, 3, -2}}; fdet[M] Det[M]

import numpy as np def fdet(M): n = len(M) if n == 2: return M[0][0]*M[1][1] - M[0][1]*M[1][0] else: return sum([(-1)**(i + 1)*M[0][i]*fdet(np.delete(M[1:],i,1)) for i in range(n)]) M = [[1, 1, 3, 7], [4, 4, 5, 0], [1, 5, 5, 6], [1, -4, 3, -2]] print("fdet(M):",fdet(M)) print("np.linalg.det(M):",np.linalg.det(M))

You can check the section on the determinant of a matrix for additional information on some of the properties of the determinant of a matrix.

### Solving Systems of Linear Equations

Solving systems of linear equations has been the subject of study for many centuries. In particular, for every engineering discipline and almost every engineering application, systems of linear equations appear naturally with large numbers of unknowns. For example, the stiffness method in structural analysis as well as the finite element analysis method seek to find the solution of the linear system of equations where is a symmetric matrix of dimensions , is a vector of external forces and is the vector of the displacement of the structure nodes. The software used need to implement a method by which can be obtained given particular values for . An appropriate method to solve for a linear system of equations has to be computationally efficient. In the following, we will present a few methods to solve systems in which the number of equations is equal to the number of unknowns along with their pros and cons. The methods are categorized into “Direct Methods” and “Iterative Methods”

In the banded matrix, how to understand “The band width is the maximum number of columns on the same row that have non-zero entries.” If I have a matrix [1,1,0,0,0][1,1,0,0,0][0,0,1,0,0][0,0,0,1,1][1,1,0,1,1], the band width is two or three?

The matrix you provided isn’t a good example as the bottom row contains nonzero values at the first and last element.

If the last row was [0,0,0,1,1] then the bandwidth would be 3.

Yes, Dr. Adeeb. That was my mistake. If my matrix is [1,1,0,0,0][1,1,0,0,0][0,0,1,0,0][0,0,0,1,1][0,0,0,1,1], I agree that the bandwidth for this matrix would be 3. But the maximum number of columns on the same row that have non-zero entries is only 2?

Hi Lei,

You are right. We will modify the definition to account for examples like the one you presented.

Samer