haihongyuan.com

海量文库 文档专家

海量文库 文档专家

发布时间：2013-10-23 13:44:15

Mathematical Methods (10/24.539)

III. Overview of Linear Algebra

Introduction

The subject of Linear Algebra, in general, covers a broad range of topics. Our goal in this unit is simply to review the standard concepts needed for other subjects in this course. In particular, we will first cover the basic notation and operations associated with vector and matrix algebra and then focus on systems of linear equations, including both inhomogeneous and homogeneous equations. The homogeneous systems, of course, also lead to the important subject of

eigenvalues and eigenvectors of a matrix. The classification of matrices based on the properties of their eigenvalues and eigenvectors is also discussed briefly. Finally, a demo is provided to illustrate how to perform many of the analytical operations outlined in this unit within the Matlab programming language.

The subjects reviewed here are treated as part of most undergraduate engineering programs (although you may not have had a formal course in Linear Algebra). As such, this section of notes is primarily intended as review material. Students already comfortable with this subject material should quickly browse this section to become familiar with the specific notation used here, and also to become acquainted with performing many common and very useful matrix-vector operations within the Matlab environment. Students weak in this subject are encouraged to study these notes thoroughly and to consult other reference books on this subject as needed. The key topics treated here are: ? General Notation

? Gauss Elimination

? Determinant of a Matrix

? Matrix Inverse

? Rank of a Matrix

? The Case of n Equations and n Unknowns ? Overview

? An Example ? Three Special Classes

? Quadratic Forms

? Similar Matrices

Math Methods -- Section III: Overview of Linear Algebra 2

Basic Notation and Operations

This section introduces some terminology and notation from linear algebra and also outlines some basic arithmetic operations with vectors and matrices. Let’s start by defining some notation associated with vectors and matrices.

Note: In the technical literature, vectors and matrices are usually written with bold lower and upper case letters or as variables with a single underline or double underline, respectively, for 1-D vectors or 2-D matrices. In my courses, I use both of these notation schemes so that the students become familiar with a variety of forms for representing these quantities. In this section, however, I have tried to use the underline notation consistently so that it is not too confusing for the student who has not used their linear algebra background for some time…

A vector is simply an ordered set of numbers or quantities. A column vector is usually written as ?x1?

=?x2? ????x3??

and a row vector is given by =[x1x2Tx3]

where the length of the vector is equal to the number of elements. The usual notation, without the superscript T, refers to the multiple row, single column format - thus, the vector quantity is referred to as a column vector. Similarly, the row vector has only one row but multiple columns. ?x1??y1?

Given two column vectors, =?x2? and y=?y2?, the most common arithmetic operations are ???????x3???y3??

defined as follows:

Addition ?x1+y1?

=+y=?x2+y2? or zi=xi+yi ????x3+y3??

?αx1?

=α=?αx2? or zi=αxi ????αx3?? (3.1) Multiplication by a Scalar (3.2)

Dot Product (inner product) α=?y=[x1x2?y1?x3]?y2?=x1y1+x2y2+x3y3????y3??orα=y=∑xiyi (3.3) iT

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 3Outer Product ?x1?

T==?x2?[y1y2???x3????x1y1x1y2y3]=?x2y1x2y2??x3y1x3y2?

x1y3?x2y3? ?x3y3?? (3.4) or =??aij?? where aij=xiyj

A matrix is a regular 2-D array of numbers or quantities and is denoted with a double underline, =??aij??, =??bij??, etc.

where i is the row index and j is the column index. For example, a 3x3 matrix can be written as ?a11a12

=?a21a22???a31a32a13?a23? ?a33??

Again, many of the common arithmetic operations with matrices are as follows:

Addition C=+ or cij=aij+bij (3.5) Scalar Multiplication =α or cij=αaij (3.6) Matrix Multiplication C= or cij=∑aikbkj

k (3.7)

where the number of columns of the first matrix must be equal to the number of rows of the second matrix, or × = (m×n)(n×p)=(m×p)

where the notation m×n, for example, implies that the matrix has m rows and n columns. Matrix-Vector Multiplication y= or yi=∑aijxj

j (3.8)

Matrix Transpose =T or cij=aji (3.9) Also there are a number of special matrices of interest. For example, some of these matrices include diagonal, triangular, square, and identity matrices, as well as symmetric and skew

symmetric matrices, etc.. Most of the names for these matrices are self-explanatory. A square

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 4matrix is one with an equal number of rows and columns. A lower triangular matrix is a square matrix with all zero elements above the diagonal elements. Also, a real symmetric matrix is one that satisfies T= or aji=aij

T=? or aji=?aij (3.10) and a real skew-symmetric matrix satisfies the relationship (3.11) Other relationships will be defined as needed in subsequent subsections.

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 5

Systems of Linear Algebraic Equations

General Notation

The major motivation for the matrix/vector notation outlined in the previous section is as a shorthand representation for linear systems of algebraic equations. The system of equations

a11x1+a12x2+"+a1NxN=b1

a21x1+a22x2+"+a2NxN=b2

#

aN1x1+aN2x2+"+aNNxN=bN (3.12)

can be written in matrix notation as

?a11a12"a1N??x1??b1??a?????"aa21222N???x2?=?b2? ???#??#?##??????"aaa?N2NN??N1??xN??bN? (3.13)

and, using the definitions of matrix multiplication, we have = (3.14) Gauss Elimination

Most direct methods for solving systems of equations involve a sequence of elementary row operations. These operations represent legal algebraic manipulations that do not alter the basic equality associated with the original equations. The purpose of the row operations is to take the original equations and put them into a form that is easier to solve than the original equations. There are three row operations that are used to systematically simplify the original system of equations:

1. Interchange two rows. 2. Multiply a row by a constant. 3. Add a constant times one row to another row.

The Gauss Elimination Method is the most well known method that implements these row operations in a systematic manner to take the original system and convert the matrix to upper triangular form. In this form, back substitution is used to evaluate the unknown solution vector . The elimination step can be represented symbolically using an augmented matrix notation, ??=??, or, for example, a 3x3 system would be transformed as follows: ??

?xxxx??xxxx??xxxx???0xxx? ???????xxxx???00xx??

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 6where the x notation implies a general entry and the last column in the original matrix contains the right hand side vector . Of course, after transformation, the entries in the resultant matrix are different from the original case. However, this upper triangular form (for the n×n part of the augmented matrix), which is also known as echelon form, is an equivalent representation of the original equation. Once in this form, one can easily use back substitution to solve for the unknown vector .

As a simple example of this method, consider the following 3x3 system: = b

?219??x1??1???23?1??x?=?2?

???2?????421????0???x3???

?2191???23?12? ????4210??

?2191??0483? ????4210??

1??219?0483? ????00?17?2??

?22= ?1717 Written in augmented matrix form, this becomes Now, as our first row operation, take row 1 added to row 2 to give Note that only row 2 is modified in this step. Now take -2 times row 1 added to row 3 to give This system is now in echelon form. Using back substitution gives

x3=x2=x1=[3?8x3]=35 468[1?x2?9x3]=?239 136

A quick check shows that this is indeed the correct solution to the original system of equations. The reader is referred to the section on Numerical Solution of Algebraic Equations (Section VI of these Lecture Notes) for a more detailed treatment of the Gauss Elimination Algorithm and other techniques for solving systems of linear algebraic equations on the computer.

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 7Determinant of a Matrix The determinant of a matrix, denoted as det or , appears frequently in applications of matrix equations. It is sometimes thought of as a measure of the size or magnitude of a matrix. Independent of its formal interpretation, it does appear in many formal definitions of other quantities and we must be able to compute det in lots of situations. For hand manipulation of low order systems, Laplace’s expansion for det is the best way to evaluate this quantity (computer computation is done differently and more efficiently by other means). Laplace’s expansion can be written in terms of an expansion along any row i as det=∑aijcij for any i

j (3.15)

or down any column j as det=∑aijcij for any j

i (3.16)

where cij is the cofactor of element aij. The elements of the cofactor matrix are defined as

cij=(?1)i+jMij (3.17) where Mij is referred to as the minor of the aij element. Mij is defined as the determinant of the matrix formed by deleting the ith row and the jth column from the original matrix. For example, given a general 3x3 matrix ?a11a12

=?a21a22???a31a32a13?a23? ?a33??

we can expand down column 1 (for example), giving

where

det=a11c11+a21c21+a31c31 c11=(+1)M11=a22

a32

a12

a32a23a33=a22a33?a23a32 =?a12a33+a13a32 c21=(?1)M21=?

c31=(+1)M31=a13a33a13

a23 a12a22=a12a23?a13a22

Note that this is exactly the same result as if one expands along row 1 (or any other row or column).

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 8The determinant of a matrix may or may not be altered under certain variations to the original matrix. Several important relations are as follows: 1. The det is not altered if the rows are written as columns in the same order. Therefore,

det=det T (3.18) 2. If any two rows or columns are interchanged, the value of det is multiplied by -1. 3. The value of det is not altered if the elements of one row are altered by adding any constant multiple of another row to them.

4. The determinant is multiplied by a constant α if any row is multiplied by α.

5. The determinant of a diagonal matrix is simply the product of the diagonal elements. This is also true for triangular matrices. 6. For square matrices,

det()=det()=det

Matrix Inverse (3.19)

The matrix inverse, denoted as , is a quantity used in the formal manipulation and solution of systems of equations. is defined such that ==. This says that a square

matrix multiplied by its inverse gives the identity matrix. Also, the identity matrix operating on a matrix or vector of appropriate size does not alter the original quantity. These facts can be used to write the formal solution to a system of equations. In particular, given =, a formal solution for can be developed as follows: Starting with =, pre-multiply both sides by to give

?1?1?1?1?1?1= ?1?1but =, and =, therefore we have = ?1 (3.20) This formal solution is very important, since it provides a basis for discussing the uniqueness and existence of solutions and it also allows for various manipulations of matrix equations.

However, the reader should be cautioned that this formulation is not the most efficient procedure for actually computing the solution vector . For computer implementation, especially for large systems, other techniques are far more efficient (see Section VI on Numerical Solution of Algebraic Equations).

There are many cases, however, when it is useful to actually evaluate the inverse matrix. There are a variety of ways to do this. For low order systems, the following formula is often applied, CT

=det?1 (3.21)

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 9where C is the matrix whose elements are the cofactors of automated implementation on the computer, some form of the Gauss-Jordan Method is often used. The Gauss-Jordan Elimination Method (which is just an extension of the Gauss

Elimination technique discussed earlier) applies elementary row operations to transform the original augmented matrix as follows:

?xxx100??100xxx??xxx010???010xxx? ???????xxx001???001xxx??

With this symbolic notation, we see that the original matrix is augmented with the identity

matrix. Extending the notation from before, this says we are trying to evaluate a matrix equation of the form, =, for the unknown matrix inverse matrix, that =. We can solve for by performing row operations on the augmented matrix ????. ?, finally putting it into the form ???

Let’s illustrate these two methods for finding the inverse matrix using the following 3x3 matrix, ?3?22?A=?12?3? ????412???1

Method I: Using eqn. (3.21) let’s first find det by expanding along row 1, or det=32?31?312+2+2=3(7)+2(14)+2(?7)=35 124241

Also the cofactor matrix is given by ?7?14?7?=?6?2?11? ??8???211?

62??7TC1?1=??14?211? =?det35????7?118??

?1?Therefore, and a quick check on = gives

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 10 62??3?22??7?3500?1?1?14?211??12?3?=?0350?= ????35?35??????7?118????412???0035?

which shows that all the manipulations have been done correctly!

Method II:

For the Gauss-Jordan method, we start with the original matrix augmented with the 3x3 identity matrix, or

?3?22100??12?3010? ????412001??

Now let’s systematically perform a set of row operations to transform this matrix into the desired form. To start, take -4/3 times row 1 added to row 3, giving 2100??3?2?12?3010? ????0?3?4301??

2100??3?2?03?3?310? ????0?3?301??

2100??3?2?0?3?310? ????1???00?

300??1?2323?01?8?0? ??01?735????0?Now take -1/3 times row 1 added to row 2, to give Taking -11/8 times row 2 added to row 3 gives Now if each row is normalized, we have

Continuing to perform row operations to eliminate the upper triangular terms, we take -2/3 times row 3 added to row 1 to give 04922???1?23?01??80? ??01?735????0?

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 11Then 11/8 times row 3 added to row 2 gives ?1?230?16??010??235? ??01?735?35835???0?

235??100735?010??23535? ????001?735?3535??

62??71?1=??14?211? ?35????7?118??Finally, 2/3 times row 2 added to row 1 gives Therefore,

which is the same result obtained from Method I (as expected).

A couple of convenient relationships that should also be noted are as follows: 1. If is a diagonal matrix (a square matrix with all zeros in the off-diagonal locations), then

?1? ?1=?aii?? (3.22)

2. The inverse of a product of matrices is simply the product of the individual inverses in the opposite order, or ()?1= ?1?1 (3.23) To show this last relationship (as an example of manipulating matrix equations), we have

()=C ()()== ?1?1

Thus =?1, or =?1?1, which proves the above statement.

Rank of a Matrix

The rank of a matrix is defined as the maximum number of linearly independent rows or columns in the matrix. It is important to note that elementary row operations do not alter the Trank of a matrix. Also it should be noted that and have the same rank.

Given m equations (i.e. m rows) with n unknowns (i.e. n columns), ??=?? = or in augmented form ??

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 12one can make the following statements concerning the existence and uniqueness of solutions for this matrix system: ?? are equal. 1. This system has nontrivial solutions only if rank and rank 2. The system has precisely one solution if rank is n, where n is the number of unknowns in vector . 3. The system has infinitely many solutions if rank is less than n.

In general, if m > n, we have an over-determined system, and usually no solutions exist. If rank is m, then there are m linearly independent rows and only n unknowns; thus, there are no nontrivial solutions that can satisfy m independent equations with n unknowns (with n < m). In this case one usually uses the method of least squares to find the best solution based on some specific objective criterion (the reader is referred to the literature for further information on this subject).

If m < n, we have an under-determined system and usually an infinite number of solutions will satisfy these conditions. If m = n (i.e. a square matrix) and rank = m = n, there is a single unique solution. This is normally the case of interest. If =0 (homogeneous system), then for a nontrivial solution, rank A must be less than n. This says that the system matrix must have linearly dependent rows (which implies that the determinant is zero - see below).

The Case of n Equations and n Unknowns

For the usual case of n simultaneous equations with n unknowns, we have = and =?1where?1CT

= detNow two situations can occur:

I. Non-Homogeneous Problems: In this case, ≠0, and this system is said to be a non-homogeneous system. For this situation, there is only a single non-trivial solution if we have n linearly independent rows, which implies ?1?1that rank = n, that the det is nonzero, and that exists. When exists, is said to

be non-singular.

II. Homogeneous Problems: If =0 , then = implies, at first glance, that must be the null vector since we are multiplying the inverse matrix and the =0 vector. However, if det=0, then does not exist, and the solution form, =, leads to an indeterminate form, which could lead to a nontrivial solution. In fact, this is indeed the situation, and we can argue that there are nontrivial

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008) ?1?1?1

Math Methods -- Section III: Overview of Linear Algebra

?113solutions only if does not exist. In this case we say that is a singular matrix. This happens only if det=0 which implies that the rows of are linearly dependent and that rank <n.

These conditions for homogeneous problems are very important in practice, and they lead

naturally to the discussion of Eigenvalue-Eigenvector problems, which will be the next subject in this review unit on Linear Algebra.

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 14

Eigenvalue/Eigenvector Problems

Overview

From the discussion in the previous subsection on Systems of Linear Algebraic Equations, we saw that homogeneous equations with n equations and n unknowns require that the system matrix be singular for the existence of nontrivial solutions. The classical eigenvalue problem is a special case that falls into this class of problems and it arises from the general problem given by = when =λ (that is, the right hand side vector is some constant times the solution vector ). With this substitution, we have =λ (3.24) These systems occur frequently in applications and are usually written as (?λ)=0

det(?λ)=0 (3.25) which is a homogeneous system of equations. Therefore, for non-trivial solutions, we require that (3.26) which is referred to as the characteristic equation. This gives rise to an nth order polynomial in λ which has n roots -- the n eigenvalues of a square matrix of order n.

Note that the eigenvalues may be real and distinct, complex conjugates, repeated, or some combination of these. Note also that the sequence λ1,λ2,"λn is called the eigenvalue spectrum, with the magnitude of the largest eigenvalue denoted as the spectral radius, or λmax=spectralradius The eigenvector associated with the ith eigenvalue, λi, is found by evaluating the homogeneous equation (?λi)i=0 (3.27) An Example

As an example, let’s find the eigenvalues and eigenvectors of the following matrix: ?2?10?A=??12?1? ????0?12??

2?λ?10

?λ=?12?λ?1=0

?12?λ0The characteristic equation is given by

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 15Expanding the determinant along row 1 using Laplace’s expansion gives ?λ=λ3?6λ2+10λ?4=0

and the roots of this 3rd order polynomial are (obtained from Matlab)

λ1=2 and λ2,3=2±

Now, the eigenvector associated with the ith eigenvalue can be determined by solving the matrix equations with the specific eigenvalue inserted into the equation. For example, for λ1=2, we have

?0?10??x1??0???10?1??x?=?0? ???2?????0?10????0???x3??1?

?x2=0 , ?x1?x3=0 , and ?x2=0 which gives three equations

Clearly, the first and third equations are redundant, as expected. These equations, along with the second equation, which implies that x3=?x1, identify the first eigenvector as ?1?=?0? ?????1??

where we have chosen the first component to be unity. Clearly there is an arbitrary

normalization associated with the eigenvector (because a homogeneous system of rank n-1 will always have an infinite number of solutions that simply differ by a single normalization

parameter). One common practice is to normalize the magnitude of the vector to unity to force some specificity for the normalization constant. If this is done, the above eigenvector becomes

?1??==0 ??1??

are valid eigenvectors for this eigenvalue (differ only by a normalization). Note Both and that normalization of the eigenvectors is usually not a requirement in most applications -- it is often done, however, in computer calculations for consistency among various computer codes.

For λ2=2+

????1???0?1?10??x1??0?????1?x2=?0? ?????x??0??3?2??

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 16

or

1?x2=0 , ?x12?x3=0 , and ?x2?3=0

and these give the relations

x1=and x3=

1 = x3 and x2 is the arbitrary normalization. For convenience, we choose x2

=, which gives

?1??=?

?

1???

?1?=

?1???Similarly, the third eigenvector can be determined to be

using the same method as above.

Summary Note

The capability to do computations of this type is built directly into Matlab and other similar programs and, in practice, automated routines like those in Matlab (see the Matlab demo in a later subsection) are used in day-to-day engineering applications as needed. However, the student should definitely know the fundamentals of these numerical algorithms (although the details are not always necessary). By assuring that you can do the above manipulations by hand for low order systems, you will gain the confidence and experience necessary to intelligently and efficiently use the automated software. Thus, you should make sure you understand the above example, and be able to perform similar manipulations on small systems as verification of the computer tools that simply automate the procedures.

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 17

Some Special Matrices

Three Special Classes

There are a number of matrices that deserve some special mention. In particular, of interest here are three classes of matrices -- Hermitian, Skew-Hermitian, and Unitary Matrices.

Hermitian matrices satisfy the relationship ??T= or a??ji=aij (3.28) where the wavy line over an element implies that one should take the complex conjugate of that quantity. An example of a hermitian matrix is 1?3i??4=?? 1+3i7??

??ii=aii for the Note that the diagonal elements of hermitian matrices must be real, since a

diagonal elements.

Skew-hermitian matrices are similar to the above definition except for a negative relationship, ??T=? or a??ji=?aij (3.29)

??ii=?aii along the diagonal. In this case, the diagonal elements must be pure imaginary, since a

This really says that (α?jβ)=?(α+jβ), which clearly implies that α=0. As an example, consider the following matrix, 2+i??3i =????2+i?i?

??T=?1 A unitary matrix is one that satisfies the expression (3.30) ??1As an example, if

? and ????T. As a check, let’s compute the product ??T and see if it gives the should be the same as identity matrix, or

Note that hermitian, skew-hermitian, and unitary matrices are, in general, complex matrices. However, a subset of each of these classes exists for the case of all real elements, and they go by the names symmetric, skew-symmetric, and orthogonal, respectively.

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 18The nice thing about matrices within these classes is that we can characterize their eigenvalue spectrum, as follows:

1. The eigenvalues of a hermitian (or real symmetric) matrix are real.

2. The eigenvalues of a skew-hermitian (or real skew-symmetric) matrix are imaginary or zero.

3. The eigenvalues of a unitary matrix (or real orthogonal) matrix have absolute value of unity. For the examples given above we can compute the eigenvalues, giving

Hermitian matrix λ2?11λ+18=0 and λ1,2=9,2

λ2?2iλ+8=0 and λ1,2=4i,?2i

λ2?iλ?1=0 and λ1=1

2Skew-hermitian matrix Unitary matrix

+i,λ2=)1i 2()

where this last set of eigenvalues was obtained from Matlab. Also note that the magnitude of each eigenvalue for the unitary matrix is indeed unity. For example, the magnitude of λ

1 is given by

λ1===1 Quadratic Forms The form is a common combination of terms that occurs frequently in applications. In particular, if and are both real, then the combination is referred to as a quadratic form. Also if is hermitian, then is real for any , and if is skew-hermitian, then TTT

is pure imaginary for any . These summary properties can be useful in some cases. Similar Matrices

One final set of terminology related to the eigenvalues of a matrix still needs to be discussed – that is the concept of similar matrices and related subjects. In particular, two matrices,

A and B, are said to be similar if they satisfy the relation T= ?1 (3.31) where is a transformation matrix. This transformation is said to be a Similarity

Transformation. The important point here is that similar matrices have the same eigenvalues. In addition, if is an eigenvector of , then y=?1 is the eigenvector of corresponding to that same eigenvalue. We can show this by the following manipulations:

=λ =λ

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008) ?1?1

Math Methods -- Section III: Overview of Linear Algebra 19

=λ =λ =λy ?1?1?1?1?1

This set of expressions shows that λ is indeed an eigenvalue of and that y=?1 is the eigenvector of that corresponds to eigenvalue λ.

If λ1,λ2,"λn are distinct eigenvalues of an n×n matrix, then the corresponding eigenvectors ,2,3,"form a linearly independent set and they represent a basis of eigenvectors in n dimensional space.

The modal matrix is a special matrix whose columns contain the linearly independent eigenvectors/basis vectors, or =[2"n] (3.32) Also we should note that any vector, y, has a unique representation in n dimensional space simply as a linear combination of the basis vectors, or y=c1+c2+c33+"cnn (3.33) Also note that a linear transformation, =, in terms of the basis vectors, becomes

or =c1λ1+c2λ2+"cnλnn (3.34) ==[c1+c2+c33+"cnn] Now if we let the transformation matrix, , in the above similarity transformation expression

[see eqn. (3.31)] be composed of the basis vectors for the n-dimensional problem, or

then, ==[2"n] ?1= (3.35) which is a diagonal matrix with the eigenvalues of along the diagonal of similar relationship that is often used is = ?1 (3.36)

A proof of the first relationship can be demonstrated as follows: =[2"n]=[λ1λ2"λnn]

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 20

=[2?λ1000??0λ00?2? "n]??00%0???000λn??

or = and = as given above. ?1

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra 21

A Matlab Demo

A short Matlab demo has been prepared to illustrate some of the matrix/vector operations that can be performed within this programming environment. A few quantities are defined ?2?=?1? ?????1???0? y=??4? ????3???105? =?04?2? ????132???6?22? =?? 832??

and then several manipulations are performed with these variables and related quantities. The Matlab commands are stored in the file linademo.m and a diary file is created during the run and saved as linademo.out. The actual m-file has several comments and it also displays (via the disp command) various comments to the output diary file. With this information, the Matlab file is very easy to follow and is quite self-explanatory. These files (the main program linademo.m and the diary file linademo.out) are listed in Table 3.1 and Table 3.2, respectively.

This demo only touches on a few of the matrix operations that can be accomplished with the Matlab package. If you are a new Matlab user, you should use this as a start, and then build upon this capability as needed for specific applications. The Matlab documentation is a good source of information as you become more experienced and your needs grow. I think you will find that Matlab is extremely powerful and quite easy to use for typical linear algebra

applications.

Table 3.1 Listing of Matlab file linademo.m.

%

% LINADEMO.M Linear Algebra Applications in MATLAB

%

% This file simply demonstrates several linear algebra operations that can be

% performed in Matlab. This area is, in fact, one of Matlab's greatest strengths,

% since the base element is a 2-d array and all operations are, by default, matrix

% manipulations. In addition to the basic arithmetic operations, Matlab also has

% m-files for just about any matrix application or operation you can imagine.

% This demo just illustrates a few of Matlab's capabilities.

%

% File prepared by J. R. White, UMass-Lowell (August 2008).

%

%

% Getting started

clear all, close all

%

% Open diary file for saving solutions

delete linademo.out

diary linademo.out

format compact

disp(' *** LINADEMO.OUT *** Diary File for LINADEMO.M ')

disp(' ')

%

% Define some matrices for the sample problems which follow

disp('Matrices for sample manipulations')

x = [2 1 -1]', y = [0 -4 3]'

A = [1 0 5; 0 4 -2; 1 3 2], B = [6 -2 2; 8 3 2]

%

% Now let's perform several arithmetic operations

disp('Find inner product of x and y'); xx = x'*y

disp('Find outer product of x and y'); XX = x*y'

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra

disp('Try getting the row and column dimensions of XX'); [nr,nc] = size(XX) disp('Note that A*B is undefined, but we can do B*A'); C = B*A

disp('What is the size of B transposed * B?'); size(B'*B)

disp('How about the size of B * B transposed?'); size(B*B')

%

% We can also extract portions of a matrix (using the repeat operator (the :) ) disp('The first column of A is'); a1 = A(:,1)

disp('Or the first and third rows of A can be extracted'); a13 = A(1:2:3,:) %

% Working with systems of equations is also easy

disp('The rank of A is'); rankA = rank(A)

disp('The determinant of A is'); detA = det(A)

disp('The inverse of A is'); invA = inv(A)

disp('The solution to Az = y can be found as z = invA*y'); z1 = invA*y disp('Or, more efficiently, with an LU decomposition scheme'); z2 = A\y

disp('We can see the components of the LU decomp scheme'); [L,U,P] = lu(A) disp('With this form, we should have L*U = P*A, or L*U - P*A = 0'); ZZ = L*U-P*A %

disp(['Also if you do not know how to use a command, just type ' ...

'"help command name".']);

disp('For example, help lu gives'); help lu

%

% Finding eigenvalues and eigenvectors is also straightforward

disp('The eigenvalues & eigenvectors of A are'); [M,D] = eig(A)

disp(['For distinct eigenvalues, M should satisfy the similarity ' ...

'transformation, D = invM*A*M. Let us see!']); DD = inv(M)*A*M

%

% Well this demo could go on and on, so let's finish by simply closing the diary file disp('And so on, and so on, and so on, ...');

diary off

%

% end of demo

22

Table 3.2 Listing of diary file linademo.out from linademo.m.

*** LINADEMO.OUT *** Diary File for LINADEMO.M

Matrices for sample manipulations

x =

2

1

-1

y =

-4

3

A =

1 0 5

0 4 -2

1 3 2

B =

6 -2 2

8 3 2

Find inner product of x and y

xx =

-7

Find outer product of x and y

XX =

0 -8 6

0 -4 3

0 4 -3

Try getting the row and column dimensions of XX

nr =

3

nc =

3

Note that A*B is undefined, but we can do B*A

C =

8 -2 38

10 18 38

What is the size of B transposed * B?

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra

ans =

3 3

How about the size of B * B transposed?

ans =

2 2

The first column of A is

a1 =

1

1

Or the first and third rows of A can be extracted

a13 =

1 0 5

1 3 2

The rank of A is

rankA =

3

The determinant of A is

detA =

-6

The inverse of A is

invA =

-2.3333e+000 -2.5000e+000 3.3333e+000

3.3333e-001 5.0000e-001 -3.3333e-001

6.6667e-001 5.0000e-001 -6.6667e-001

The solution to Az = y can be found as z = invA*y

z1 =

20

-3

-4

Or, more efficiently, with an LU decomposition scheme

z2 =

20

-3

-4

We can see the components of the LU decomp scheme

L =

1.0000e+000 0 0

0 1.0000e+000 0

1.0000e+000 7.5000e-001 1.0000e+000

U =

1.0000e+000 0 5.0000e+000

0 4.0000e+000 -2.0000e+000

0 0 -1.5000e+000

P =

1 0 0

0 1 0

0 0 1

With this form, we should have L*U = P*A, or L*U - P*A = 0

ZZ =

0 0 0

0 0 0

0 0 0

Also if you do not know how to use a command, just type "help command name". For example, help lu gives

LU LU factorization.

[L,U] = LU(A) stores an upper triangular matrix in U and a

"psychologically lower triangular matrix" (i.e. a product of lower triangular and permutation matrices) in L, so that A = L*U. A can be rectangular.

[L,U,P] = LU(A) returns unit lower triangular matrix L, upper triangular matrix U, and permutation matrix P so that P*A = L*U.

[L,U,p] = LU(A,'vector') returns the permutation information as a vector instead of a matrix. That is, p is a row vector such that A(p,:) = L*U. Similarly, [L,U,P] = LU(A,'matrix') returns a

permutation matrix P. This is the default behavior.

Y = LU(A) returns the output from LAPACK'S DGETRF or ZGETRF routine if

A is full. If A is sparse, Y contains the strict lower triangle of L embedded in the same matrix as the upper triangle of U. In both full and sparse cases, the permutation information is lost.

[L,U,P,Q] = LU(A) returns unit lower triangular matrix L, upper 23

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008)

Math Methods -- Section III: Overview of Linear Algebra

triangular matrix U, a permutation matrix P and a column reordering

matrix Q so that P*A*Q = L*U for sparse non-empty A. This uses UMFPACK

and is significantly more time and memory efficient than the other

syntaxes, even when used with COLAMD.

[L,U,p,q] = LU(A,'vector') returns two row vectors p and q so that

A(p,q) = L*U. Using 'matrix' in place of 'vector' returns permutation

matrices.

[L,U,P,Q,R] = LU(A) returns unit lower triangular matrix L, upper

triangular matrix U, permutation matrices P and Q, and a diagonal

scaling matrix R so that P*(R\A)*Q = L*U for sparse non-empty A.

This uses UMFPACK as well. Typically, but not always, the row-scaling

leads to a sparser and more stable factorization. Note that this

factorization is the same as that used by sparse MLDIVIDE when

UMFPACK is used.

[L,U,p,q,R] = LU(A,'vector') returns the permutation information in two

row vectors p and q such that R(:,p)\A(:,q) = L*U. Using 'matrix'

in place of 'vector' returns permutation matrices.

[L,U,P] = LU(A,THRESH) controls pivoting in sparse matrices, where

THRESH is a pivot threshold in [0,1]. Pivoting occurs when the

diagonal entry in a column has magnitude less than THRESH times the

magnitude of any sub-diagonal entry in that column. THRESH = 0 forces

diagonal pivoting. THRESH = 1 is the default.

[L,U,P,Q,R] = LU(A,THRESH) controls pivoting in UMFPACK. THRESH is a

one or two element vector which defaults to [0.1 0.001]. If UMFPACK

selects its unsymmetric pivoting strategy, THRESH(2) is not used. It

uses its symmetric pivoting strategy if A is square with a mostly

symmetric nonzero structure and a mostly nonzero diagonal. For its

unsymmetric strategy, the sparsest row i which satisfies the criterion

A(i,j) >= THRESH(1) * max(abs(A(j:m,j))) is selected. A value of 1.0

results in conventional partial pivoting. Entries in L have absolute

value of 1/THRESH(1) or less. For its symmetric strategy, the diagonal

is selected using the same test but with THRESH(2) instead. If the

diagonal entry fails this test, a pivot entry below the diagonal is

selected, using THRESH(1). In this case, L has entries with absolute

value 1/min(THRESH) or less. Smaller values of THRESH(1) and THRESH(2)

tend to lead to sparser LU factors, but the solution can become

inaccurate. Larger values can lead to a more accurate solution (but

not always), and usually an increase in the total work and memory

usage.

[L,U,p] = LU(A,THRESH,'vector') and [L,U,p,q,R] = LU(A,THRESH,'vector')

are also valid for sparse matrices and return permutation vectors.

Using 'matrix' in place of 'vector' returns permutation matrices.

See also colamd, luinc, qr, rref, umfpack.

Overloaded functions or methods (ones with the same name in other directories)

help gf/lu.m

Reference page in Help browser

doc lu

The eigenvalues & eigenvectors of A are

M =

-9.5897e-001 -7.2968e-001 -7.2968e-001

1.1859e-001 2.2243e-001 -4.2444e-001i 2.2243e-001 +4.2444e-001i

2.5750e-001 -3.8983e-001 -2.9322e-001i -3.8983e-001 +2.9322e-001i

D =

-3.4256e-001 0 0

0 3.6713e+000 +2.0092e+000i 0

0 0 3.6713e+000 -2.0092e+000i

For distinct eigenvalues, M should satisfy the similarity transformation, D = invM*A*M. Let us see!

DD =

-3.4256e-001 +2.4652e-032i 1.6170e-015 +5.3363e-016i 1.5472e-015 -1.3260e-015i

-4.4409e-016 +4.4409e-016i 3.6713e+000 +2.0092e+000i -5.5511e-016 -8.8818e-016i

-3.3307e-016 -4.1633e-016i -8.0491e-016 +9.4369e-016i 3.6713e+000 -2.0092e+000i

And so on, and so on, and so on, ...

Lecture Notes for Math Methods by Dr. John R. White, UMass-Lowell (August 2008) 24