Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » A First Course in Electrical and Computer Engineering » Linear Algebra: Solving Linear Systems of Equations

Navigation

Table of Contents

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS

    This collection is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing Society

    Click the "IEEE-SPS" link to see all content they endorse.

  • College Open Textbooks display tagshide tags

    This collection is included inLens: Community College Open Textbook Collaborative
    By: CC Open Textbook Collaborative

    Comments:

    "Reviewer's Comments: 'I recommend this book as a "required primary textbook." This text attempts to lower the barriers for students that take courses such as Principles of Electrical Engineering, […]"

    Click the "College Open Textbooks" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "A First Course in Electrical and Computer Engineering provides readers with a comprehensive, introductory look at the world of electrical engineering. It was originally written by Louis Scharf […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Evowl

    This collection is included inLens: Rice LMS's Lens
    By: Rice LMS

    Comments:

    "Language: en"

    Click the "Evowl" link to see all content selected in this lens.

  • Busbee's Math Materials display tagshide tags

    This module is included inLens: Busbee's Math Materials Lens
    By: Kenneth Leroy Busbee

    Click the "Busbee's Math Materials" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Linear Algebra: Solving Linear Systems of Equations

Module by: Louis Scharf. E-mail the author

Note:

This module is part of the collection, A First Course in Electrical and Computer Engineering. The LaTeX source files for this collection were created using an optical character recognition technology, and because of this process there may be more errors than usual. Please contact us if you discover any errors.

We are now equipped to set up systems of linear equations as matrix- vector equations so that they can be solved in a standard way on a computer. Suppose we want to solve the equations from Example 1 from "Linear Algebra: Introduction" for x 1 x 1 and x 2 x 2 using a computer. Recall that Equations 1 and 2 from Linear Algebra: Introduction are

x 1 + x 2 = 85 x 1 1 . 2 = x 2 1 . 5 - 1 . 2 x 1 + x 2 = 85 x 1 1 . 2 = x 2 1 . 5 - 1 . 2
(1)

The first step is to arrange each equation with all references to x 1 x 1 in the first column, all references to x 2 x 2 in the second column, etc., and all constants on the right-hand side:

x 1 + x 2 = 85 0 . 3 x 1 - 1 . 2 x 2 = 0 . x 1 + x 2 = 85 0 . 3 x 1 - 1 . 2 x 2 = 0 .
(2)

Then the equations can be converted to a single matrix-vector equation. The coefficients form a matrix, keeping their same relative positions, and the variables and constants each form a vector:

1 1 0 . 3 - 1 . 2 x 1 x 2 = 85 0 . 1 1 0 . 3 - 1 . 2 x 1 x 2 = 85 0 .
(3)

Exercise 1

Verify by the rules of matrix multiplication that the system of equations in 2 in equivalent to the matrix equation in 3.

Equation 3 is of the general form

A x = b A x = b
(4)

where in this case

A=110.3-1.2 , x=xlx2,b=850.A=110.3-1.2 , x=xlx2,b=850.
(5)

Given any A Rn×nARn×n and bRnbRn, MATLAB can solve Equation 4 for x x (as long as a solution exists). Key ideas in the solution process are the identity matrix and the inverse of a matrix.

When the matrix A is the 1×11×1 matrix a a, the vector x x is the l-vector x x, and the vector b b is the l-vector b b, then the matrix equation A x =bAx=b becomes the scalar equation

ax=b.ax=b.
(6)

The scalar a-1a-1 is the inverse of the scalar a a, so we may multiply on both sides of Equation 6 to obtain the result

a - 1 ( a x ) = a - 1 b 1 x = a - 1 b . a - 1 ( a x ) = a - 1 b 1 x = a - 1 b .
(7)

We would like to generalize this simple idea to the matrix equation Ax=bAx=b so that we can find an inverse of the matrix A A, called A-1A-1, and write

A-1( A x ) =A-1b I x = A - 1 b . A-1( A x ) =A-1b I x = A - 1 b .
(8)

In this equation the matrix I I is the identity matrix

I= 1 0 0 ... 0 0 1 0 ... 0 0 0 1 ... 0 0 0 0 ... 1 . I= 1 0 0 ... 0 0 1 0 ... 0 0 0 1 ... 0 0 0 0 ... 1 .
(9)

It is clear that the identity matrix I I and the inverse of a matrix, A-1A-1, play a key role in the solution of linear equations. Let's study them in more detail.

The Matrix Identity. When we multiply a scalar by 1, we get back that same scalar. For this reason, the number 1 is called the multiplicativeidentity element. This may seem trivial, but the generalization to matrices is more interesting. The question is, is there a matrix that, when it multiplies another matrix, does not change the other matrix? The answer is yes. The matrix is called the identity matrix and is denoted by I I. The identity matrix is always square, with whatever size is appropriate for the matrix multiplication. The identity matrix has l's on its main diagonal and 0's0's everywhere else. For example,

I 5 = [ 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ] . I 5 =[ 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ].
(10)

The subscript 5 indicates the size. In terms of the unit coordinate vectors e i e i , we can also write the n×nn×n identity matrix as

I n = | | | e 1 e 2 ... e n | | | . I n = | | | e 1 e 2 ... e n | | | .
(11)

For any matrix ARn×pARn×p, we have

A=InA.A=InA.
(12)

For p=1p=1, we obtain the following special form for any vector xRnxRn :

x=Inx.x=Inx.
(13)

This last equation can be written as the sum

x = i = 1 n x i e i . x = i = 1 n x i e i .
(14)

This is a special case of one of the results you proved in Exercise 3 from "Linear Algebra: Matrices". Figure 1 illustrates Equation 14 and shows how the vector x x can be broken into component vectors xieixiei, each of which lies in the direction of one coordinate axis. The values of the xi'sxi's are the coordinates of xx, and their magnitudes are also the lengths of the component vectors.

Figure 1: Breaking a Vector into Components
Figure one is a three-dimensional graph with four vectors pointing in various directions. The axis pointing out towards the screen is labeled e_1, the axis pointing to the right is labeled e_2, and the axis pointing up is labeled e_3. One vector points up along the e_3 axis and is labeled e_3 x_3. Another points along the e_1 axis towards the screen and is labeled x_1 e_1. A final vector points out into the positive x_1, x_2, x_3 direction and is labeled x.

Exercise 2

Use Equation 13 and the rules for matrix multiplication to show that xRnxRn may also be written as

x = i = 1 n ( x , e i ) e i . x = i = 1 n ( x , e i ) e i .
(15)

This verifies Equation 11 from "Linear Algebra: Direction Cosines".

When the product of two numbers is 1 (the identity element), we say that they are inverses of each other, like 2 and 0.5. Likewise, we say that two square matrices are inverses of each other if their product is the identity matrix:

A B = I B = A - 1 . A B = I B = A - 1 .
(16)

An interesting and useful result is implied by this definition. Take the first form of Equation 16 and multiply by B B from the left:

A B = I B ( A B ) = B I ( B A ) B = B B A = I . A B = I B ( A B ) = B I ( B A ) B = B B A = I .
(17)

We emphasize that the inference made in the last step here is only valid when B B and A A are square matrices. The result means that, even though matrix multiplication is not commutative in general, we have a special case where it is commutative. If A A and B B are inverses of each other, then

A B = B A = I . A B = B A = I .
(18)

Exercise 3

Prove that the inverse of the 2 ×2×2 rotation matrix R(θ)R(θ) is RT(θ)RT(θ).

Matrices that are not square do not have inverses. In fact, not all square matrices have inverses. So it becomes an important issue to determine which matrices do have inverses. If a matrix has an inverse, the inverse is unique. If a square matrix has no inverse, it is called a singular matrix. The determinant of a square matrix is a scalar computed from the numbers in the matrix. It tells us whether a matrix will have an inverse or not. A matrix is singular if and only if its determinant is zero.1 In MATLAB, the notation det(A) is used to compute the determinant. Whenever the matrix A in Equation 4 is singular, it means one of two things about the system of equations represented: either the equations are inconsistent and there is no solution, or the equations are dependent and there are infinitely many solutions.

Solving A x = b A x = b. Let's now study ways to solve the matrix equation A x=bAx=b. We will assume that a unique solution for x x exists. Thus a unique matrix A-1A-1 exists with the property A-1A=IA-1A=I. The trick is to find it. Here is one procedure.

For convenience, rewrite the matrix equation Ax =b=b as

[Ab]x-1=0.[Ab]x-1=0.
(19)

The matrix [ Ab ]Rnx(n+1)[Ab]Rnx(n+1) is called the augmented matrix for the system of equations. The augmented matrix may be viewed as a systematic way of writing all the information necessary to solve the equations.

The advantage of Equation 19 is that we may premultiply both sides by any matrix C 1 C 1 (of compatible size), and the right-hand side remains zero (although this is equivalent to multiplying on both sides of Equation 4, which some may prefer). We can repeat this operation as often as we like with matrices C2,C3C2,C3, etc. The general result is

[ C m C 2 C 1 A C m C 2 C 1 b ] x - 1 = 0 . [ C m C 2 C 1 A C m C 2 C 1 b ] x - 1 = 0 .
(20)

Now suppose that we have found a sequence of matrices C1,...C1,... , C m C m that transforms the matrix A A to the identity matrix:

CmC2C1A=I.CmC2C1A=I. The augmented matrix equation in 20 simplifies to

[ I CmC2C1b] x-1=0,[ICmC2C1b]x-1=0,
(21)

which can be multiplied out to reveal that the solution for x is

x = C m C 2 C 1 b . x = C m C 2 C 1 b .
(22)

The method may be summarized as follows:

  1. form the augmented matrix [ A b ] [Ab] for the system;
  2. premultiply [ A b ] [Ab] by a sequence of selected matrices C i C i , designed to take A A to I I; and
  3. when A A is transformed to I I, b b will be transformed to x x, so the solution will appear as the last column of the transformed augmented matrix.

We may also conclude that the product of the matrices Ci must be the inverse of A since A-1A-1 is the unique matrix for which A-1A=IA-1A=I. In solving for x by this method, we have found A-1A-1 implicitly as the product CmC2C1CmC2C1.

Example 1

Consider the equation

3 1 2 4 x 1 x 2 = 6 5 3 1 2 4 x 1 x 2 = 6 5
(23)
A x = b . A x = b .
(24)

The augmented matrix for this equation is

[ A b ] = 3 1 6 2 4 5 . [ A b ] = 3 1 6 2 4 5 .
(25)

Now if we could add -2/3-2/3 times the first row to the second row, we would get 0 in the lower left corner. This is the first step in transforming A to the identity I. We can accomplish this row operation with the matrix

C 1 = 1 0 - 2 / 3 1 C 1 = 1 0 - 2 / 3 1
(26)
C 1 [ A b ] = 3 1 6 0 10 / 3 1 . C 1 [ A b ] = 3 1 6 0 10 / 3 1 .
(27)

Now adding -3/10-3/10 times the new second row to the first row will introduce 0 in the (1,2)(1,2) position, bringing us closer still to the identity. Thus

C 2 = 1 - 3 / 10 0 1 C 2 = 1 - 3 / 10 0 1
(28)
C 2 C 1 [ A b ] = 3 0 57 / 10 0 10 / 3 1 . C 2 C 1 [ A b ] = 3 0 57 / 10 0 10 / 3 1 .
(29)

We now complete the transformation to identity by normalizing each row to get the needed l's:

C 3 = 1 / 3 0 0 3 / 10 C 3 = 1 / 3 0 0 3 / 10
(30)
C 3 C 2 C 1 [ A b ] = 1 0 19 / 10 0 1 3 / 10 . C 3 C 2 C 1 [ A b ] = 1 0 19 / 10 0 1 3 / 10 .
(31)

According to the last column, the solution is

x = 19 / 10 3 / 10 . x = 19 / 10 3 / 10 .
(32)

We note in passing that the inverse of A A is the product of the C'sC's, so

A - 1 = C 3 C 2 C 1 = 1 / 3 0 0 3 / 10 1 - 3 / 10 0 1 1 0 - 2 / 3 1 = 1 / 3 - 1 / 10 0 3 / l 0 1 0 - 2 / 3 1 = 2 / 5 - 1 / 10 - 1 / 5 3 / 10 · A - 1 = C 3 C 2 C 1 = 1 / 3 0 0 3 / 10 1 - 3 / 10 0 1 1 0 - 2 / 3 1 = 1 / 3 - 1 / 10 0 3 / l 0 1 0 - 2 / 3 1 = 2 / 5 - 1 / 10 - 1 / 5 3 / 10 ·

The method we have just used, combined with a particular way of choosing the C i C i matrices, is called Gauss elimination. Gauss elimination requires less computation than finding the inverse of A because only the effect of A-1A-1 on the specific vector b b is computed. MATLAB can solve for x x by either method, as shown in Demo 4.2. For hand computations, we suggest choosing the C i C i matrices so that C 1 C 1 produces O'sO's everywhere below the diagonal in the first column, C 2 C 2 produces O'sO's below the diagonal in the second column, and so on up to Cn-1Cn-1. Then C n C n produces O'sO's above the diagonal in the nthnth column, Cn+1Cn+1 produces O'sO's above the diagonal in column n-1n-1, etc. The last one, C2n-1C2n-1, normalizes the diagonal elements to l's. We have assumed for simplicity that no O'sO's on the diagonal will be encountered in hand computations.

Exercise 4

Check that A-1A=IA-1A=I in Example 1

Exercise 5

Augment Equation 3 as in Equation 19 and use the technique of Gauss elimination to solve for x x.

Demo 1 (MATLAB). From the command level of MATLAB, solve the matrix equation of Example 1 from "Linear Algebra: Introduction" by typing

>> A = [1 1;0.3 -1.2]
>> b = [85;0]

You have entered the matrices A and b, which describe the problem. You can now solve for x by finding the inverse of A and multiplying b:

>> x = inv(A) * b

In this example the inverse is computed quickly because A is a small matrix. For a large (say, 30×3030×30) matrix, the answer would take longer to compute, and the more efficient method of Gauss elimination would reduce waiting time. You can use Gauss elimination in MATLAB by typing

>> x = A \ b

You should get the same answer. Now type the MATLAB code required to compute AxAx and to show Ax-b=0.Ax-b=0.

Exercise 6

(MATLAB) Write the following system of equations as Ax=bAx=b and solve using MATLAB:

3 ( x 1 - x 3 ) + 2 ( x 2 - 1 ) - 6 = x 3 3 ( x 1 - x 3 ) + 2 ( x 2 - 1 ) - 6 = x 3
(33)
4 x 3 = 7 x 2 - 5 4 x 3 = 7 x 2 - 5
(34)
6 ( x 1 + x 2 + 2 ) = x 3 + 1 . 6 ( x 1 + x 2 + 2 ) = x 3 + 1 .
(35)

Footnotes

  1. It is not important now to understand how the determinant is defined and computed from the elements of a matrix. In your more advanced courses you will study the determinant in some detail.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks