Linear systems of equations : Gauss elimination, Row echelon form, Linear Independence : rank of a matrix, Solutions of linear systems : Existence, Uniqueness (without proof), The matrix Eigen value Problem, Determining Eigen values and Eigen vector, Diagonalization of matrices.
Linear Systems of Equations.
A linear system of 'm' equations in 'n' unknowns x1,…,xn is a set of equations of the form:
The system is called linear because each variable xj appears in the first power only.
a11,…,amn are given numbers, called the coefficients of the system.
b1,…,bm on the right are also given numbers
Homogeneous Systems and Non-homogeneous System.
If all the bj are zero, then the system is called a homogeneous system.
If at least one bj is not zero, then the system is called a non homogeneous system.
Solutions of linear system.
A solution of the system is a set of numbers x1,…,xn that satisfies all the m equations.
If the system is homogeneous, it always has at least the trivial solution x1=0,…,xn=0.
When the system has at least one solution (one solution or infinitely many solutions) it is said to be consistent.
When the system has no solution then the system is inconsistent system.
Matrix Form of the Linear system.
Matrix form of the Linear system: From the definition of matrix multiplication we see that the m equations of the system may be written as a single vector equation.
AX=B
where the coefficient matrix A=[aij] is a m×n matrix.
are column vectors.
we assume that the coefficients aij are not all zero, so that A is not a zero matrix.
Note that x has n components, whereas B has m components.
The matrix A~=a11⋮am1⋯⋯a1n⋮amnb1⋮bm is called the augmented matrix of the system (1)
Note that the augmented matrix A~ determines the system completely because it contains all the given numbers appearing in the system.
Geometric Interpretation, Existence and uniqueness of solutions.
If m=n=2, we have two equations in two unknowns x1,x2
a11x1+a12x2a21x1+a22x2=b1,=b2
If we interpret x1,x2 as coordinates in the x1−x2 - plane, then each of the two equations represents a straight line, and (x1,x2) is a solution if and only if the point P with coordinates x1,x2 lies on both lines. Hence there are three possible cases.
(a) Precisely one solution if the lines intersect
(b) Infinitely many solutions if the lines coincide.
(c) No solution if the lines are parallel.
x1+x22x1−x2=1=0
Case (a)
x1+x22x1+2x2=1=2
Case (b)
x1+x2x1+x2=1=0
Case (c)
Gauss Elimination and Back substitution
In the Gauss elimination method, the solution to the linear system of equations is obtained by.
Step 1 : First write the given system of equations into the matrix form.
AX=B
Step 2 : By elementary row operations, the augmented matrix [AB] is brought to the upper triangular form.
Step 3 : The upper triangular system is solved using back substitution procedure by which we obtain the solution in the order xn,xn−1,xn−2,ext...,x2,x1.
Example :
The Gauss elimination method can be motivated as follows. Consider a linear system that is in triangular form (in full, upper triangular form) such as
We leave the first equation as it is. we eliminate x1 from the second equation, to get a triangular system. For this we add twice the first equation to the second, and we do the same operation on the rows of the augmented matrix.
substitute in (1)⇒x1−x2+x3=0x1=x2−x3x1=4−2∴x1=2
Elementary Row Operations.
Elementary Row Operations for Matrices:
Interchange of two rows
Addition of a constant multiple of one row to another row.
Multiplication of a row by a non zero constant 'c'
Elementary operations for Equations.
Interchange of two equations
Addition of a constant multiple of one equation to another equation
Multiplication of an equation by a non zero constant 'c'.
Row - Equivalent systems :
We now call a linear system S1 row-equivalent to a linear system S2 if S1 can be obtained from S2 by (finitely many!) row operations. This justifies Gauss elimination and establishes the following result.
Theorem.
Row - Equivalent systems
Row-equivalent linear systems have the same set of solutions.
Systems having the same solution sets are often called equivalent systems.
Gauss Elimination : The Three Possible cases of systems.
1.) Gauss elimination if unique solution exists
2.) Gauss elimination if infinitely many solutions exist.
3.) Gauss elimination if no solution exists.
Gauss Elimination if infinitely Many solutions exist
solve the following linear system of three equations in four unknowns whose augmented matrix is:
Solution: As in the previous example, we circle pivots and box terms of equations and corresponding entries to be eliminated. We indicate the operations in terms of equations and operate on both equations and matrices.
Step 1. Elimination of x1 from the second and third equations by adding
−0.6/3.0=−0.2 times the first equation to the second equation,
−1.2/3.0=−0.4 times the first equation to the third equation.
This gives the following, in which the pivot of the next step is circled.
since x3 and x4 remain arbitrary, we have infinitely many solutions. If we choose a value of x3 and a value of x4, then the corresponding values of x1 and x2 are uniquely determined.
The false statement 0=12 shows that the system has no solution.
Row Echelon form.
At the end of the Gauss elimination the form of the coefficient matrix, the augmented matrix, and the system itself are called the row echelon form. In it, rows of zeros, if present, are the last rows, and, in each non zero row, the leftmost non zero entry is farther to the right than in the previous row.
The original system of 'm' equations in 'n' unknowns has augmented matrix [A∣B]. This is to be row reduced to matrix [R∣F]. The two systems AX=B and RX=F are equivalent:
if either one has a solution, so does the other, and the solutions are identical.
At the end of the Gauss elimination (before the back substitution), the row echelon form of the augmented matrix will be,
Here, r≤m, r11=0, and all entries in the blue triangle and blue rectangle are zero.
The Rank.
The rank of a matrix in Row-Echelon form is equal to the number of non-zero rows.
The rank of a matrix is also given by the number of linearly independent rows.
If A is zero matrix, then r(A)=0If A is not a zero matrix, r(A)≥1
Note:
(a) No solution: If r is less than m (meaning that R actually has at least one row of all 0s) and at least one of the numbers fr+1,fr+2,…,fm is not zero, then the system RX=F is inconsistent: No solution is possible. Therefore the system AX=B is inconsistent as well.
(b) Unique solution. If the system is consistent and r=n there is exactly one solution, which can be found by back substitution.
(c) Infinitely many solutions. To obtain any of these solutions, choose values of xr+1,…,xn arbitrarily. Then solve the rth equation for xr (in terms of those arbitrary values), then the (r−1)st equation for xr−1 and so on up the line.
Linear Independence and Dependence of vectors.
Given any set of m vectors a(1),…,a(m) (with the same number of components), a linear combination of these vectors is an expression of the form.
c1a(1)+c2a(2)+⋯+cma(m)
where c1,c2,…,cm are any scalars. Now consider the equation.
c1a(1)+c2a(2)+⋯+cma(m)=0
clearly, this vector equation holds if we choose all cj's zero, because then it becomes 0=0. If this is the only m-tuple of scalars for which it holds, then our vectors a(1),…,a(m) are said to form a linearly independent set or, more briefly, we call them linearly independent. Otherwise, if it also holds with scalars not all zero, we call these vectors linearly dependent.
This means that we can express at least one of the vectors as a linear combination of the other vectors. For instance, if (1) holds with, say, c1=0, we can solve it for a(1):
a(1)=k2a(2)+⋯+kma(m)where kj=−cj/c1
(some kj's may be zero. Or even all of them, namely, if a(1)=0.)
Remark: Any set of m vectors a(1),…,a(m) is linearly independent if c1a(1)+c2a(2)+⋯+cma(m)=0 implies c1=c2=⋯=cm=0.
Example: Examine the linear independence of the three vectors.
a(1)a(2)a(3)=[123]=[234]=[357]
Solution:
The given three vectors are linearly dependent because
a(1)+a(2)−a(3)=[000]=0
The first two of the three vectors are linearly independent : because
c1a(1)+c1a(2)=[000]=0
implies
[c1+2c22c1+3c23c1+4c2]=[0,00]
implies
c1+2c2=0,2c1+3c2=0,and3c1+4c2=0
The first one of these equations gives c1=−2c2 which substituting on the second equation yields c2=0 which implies c1=−2c2=−2×0=0.
Hence c1=0 and c2=0.
Example: find whether the vectors
[12−13],[2−132],[−18−93]
are linearly independent.
Hence the given set of vectors is linearly independent.
Rank of a matrix
The rank of a matrix A is the maximum number of linearly independent row vectors of A. It is denoted by rank A.
The matrix
A=3−621042−212240254−15 has rank 2
first two row vectors are linearly independent,
whereas all three row vectors are linearly dependent.
We call a matrix A1 row-equivalent to a matrix A2 if A1 can be obtained from A2 by (finitely many!) elementary row operations.
Now the maximum number of linearly independent row vectors of a matrix does not change if we change the order of rows or multiply a row by a nonzero c or take a linear combination by adding a multiple of a row to another row. This shows that rank is invariant under elementary row operations:
THEOREM 1
Row-Equivalent Matrices.
Row-equivalent matrices have the same rank.
Once the matrix is in row-echelon form, we count the number of nonzero rows, which is precisely the rank of the matrix.
The last matrix is in row-echelon form and has two non zero rows. Hence rankA=2, as before.
THEOREM 2
Linear Independence and Dependence of vectors.
Consider p vectors that each have n components. Then these vectors are linearly independent if the matrix formed, with these vectors as row vectors, has rank p. However, these vectors are linearly dependent if that matrix has rank less than p.
THEOREM 3
Rank in Terms of Column vectors
The rank r of a matrix A equals the maximum number of linearly independent column vectors of A.
Hence A and its transpose AT have the same rank.
VECTOR SPACE
A vector space is a (non empty) set V of vectors with the same number of components such that with any two vectors a and b in V all their linear combinations αa+βb (α,β any real numbers) are elements of V, and these vectors satisfy the following laws:
The maximum number of linearly independent vectors in V is called the dimension of V and is denoted by dimV.
A linearly independent set in V consisting of a maximum possible number of vectors in V is called a basis for V. In other words, any largest possible set of independent vectors in V forms basis for V. That means, if we add one or more vector to that set, the set will be linearly independent.
THEOREM 6
Row space and Column space
The row space and the column space of a matrix A have the same dimension, equal to rank A.
Example: Find the rank and a basis for the row space and for the column space of the matrix.
∼100−200R3→R3+3R1
The last matrix is in row echelon form and since it has only one non zero row, rank of that matrix and hence that of the given matrix is 1.
Also, a basis for the row space of A is [1−2]
To find a basis for the column space, we find the row echelon form of AT.
∼[1000−30] by R2→R2+2R1
Hence a basis for the row space of AT is [10−3]
Hence a basis for the column space of A is 10−3
Solutions of Linear Systems: Existence, Uniqueness.
A linear system in n unknowns has a unique solution if the coefficient matrix and the augmented matrix have the same rank n, and infinitely many solutions if that common rank is less than n. The system has no solution if those two matrices have different rank.
is consistent, that is, has solutions, if and only if the coefficient matrix A and the augmented matrix A~ have the same rank. Here,
and A~=a11⋮am1⋯⋯⋯a1n⋮amnb1⋮bm
(b) Uniqueness. The system has precisely one solution if and only if this common rank r of A and A~ equals n.
(c) Infinitely many solutions. If this common rank r is less than n, the system has infinitely many solutions. All of these solutions are obtained by determining r suitable unknowns (whose submatrix of coefficients must have rank r.) in terms of the remaining n−r unknowns, to which arbitrary values can be assigned.
d.) Gauss elimination : If solution exist, they can all be obtained by the Gauss elimination. This method will automatically reveal whether or not solutions exist.
always has the trivial solution x1=0,…,xn=0. Non trivial solutions exist if and only if rank A<n. If rank A=r<n, these solutions, together with x=0, form a vector space of dimension n−r, called the solution space.
In particular, if x(1) and x(2) are solution vectors, then x=c1x(1)+c2x(2) with any scalars c1 and c2 is a solution vector. (This does not hold for nonhomogeneous systems. Also, the term solution space is used for homogeneous systems only.)
Test for consistency and solve the system of equations.
A matrix eigen value problem considers the vector equation.
Ax=λx
Here A is a given square matrix, λ an unknown scalar, and x an unknown vector. In a matrix eigen value problem, the task is to determine λ's and x's that satisfy. Since x=0 is always a solution for any λ and thus not interesting, we only admit solutions with x=0.
The solutions are given the following names: The λ's that satisfy are called eigenvalues of A and the corresponding non zero x's that also satisfy are called eigenvectors of A.
Consider multiplying non zero vectors by a given square matrix, such as,
[6437][51]=[3327],[6437][34]=[3040]
we introduce more terminology. A value of λ, for which it has a solution x=0, is called an eigen value or characteristic value of the matrix A. Another term for λ is a latent root.
("Eigen" is German and means "proper" or "characteristic".)
The corresponding solutions x=0 are called the eigen vectors or characteristic vectors of A corresponding to that eigen value λ. The set of all the eigenvalues of A is called the spectrum of A.
we shall see that the spectrum consists of atleast one eigenvalue and at most of n numerically different eigenvalues. The largest of the absolute values of the eigen values of A is called the spectral radius of A.
How to find Eigen values and Eigenvectors ?
We illustrate all the steps in terms of the matrix A=[−522−2]
By Cramer's theorem, this homogeneous linear system of equations has a non trivial solution if and only if the corresponding determinant of the coefficients is zero:
a_{11} - \lambda & a_{12} & \dots & a_{1n} \\
a_{21} & a_{22} - \lambda & \dots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \dots & a_{nn} - \lambda
\end{vmatrix} = 0$$
$A - \lambda I$ is called the characteristic matrix and $D(\lambda)$ the characteristic determinant of $A$.
$|A - \lambda I| = 0$ is called the characteristic equation of $A$. By developing $D(\lambda)$ we obtain a polynomial of $n^{\text{th}}$ degree in $\lambda$. This is called the characteristic polynomial of $A$.
**Q:-** Find the eigen values and eigen vectors of $\begin{bmatrix} 10 & 3 \\ 4 & 6 \end{bmatrix}$
characteristic equation of $A$ is $|A - \lambda I| = 0$
$$A = \begin{bmatrix} 10 & 3 \\ 4 & 6 \end{bmatrix}∣A−λI∣=10−λ436−λ=0
Eigenvalues
The eigenvalues of a square matrix A are the roots of the characteristic equation of A.
Hence a n×n matrix has at least one eigenvalue and at most n numerically different eigenvalues.
THEOREM 2
Eigenvectors, Eigenspace.
If w and x are eigenvectors of a matrix A corresponding to the same eigenvalue λ, so are w+x (provided x=−w) and kx for any k=0.
Hence the eigenvectors corresponding to one and the same eigenvalue λ of A, together with 0, form a vector space called the eigenspace of A corresponding to that λ.
Remark
Note that eigenvalues are roots of characteristic equation of a square matrix. Generally the roots need not be distinct. That is, the order of an eigenvalue as a root of the characteristic equation can be 1 or more. Also, corresponding to an eigenvalue there can be one or more number of linearly independent eigenvectors.
Algebraic Multiplicity and Geometric Multiplicity
The algebraic multiplicity, Mλ of an eigenvalue λ of matrix A is the order of λ as a root of the characteristic equation.
The geometric multiplicity, mλ of an eigenvalue λ is the number of independent eigenvectors corresponding to that eigenvalue. So geometric multiplicity is the dimension of the eigenspace corresponding to the eigen value λ
By the definition of eigenvalues and eigenvectors, an eigenvalue's geometric multiplicity must be at least one, that is, each eigenvalue has at least one associated eigenvector. Furthermore, an eigenvalue's geometric multiplicity cannot exceed its algebraic multiplicity.
Additionally, recall that an eigenvalue's algebraic multiplicity cannot exceed n.
1≤mλ≤Mλ≤n
The difference Δλ=Mλ−mλ is called the defect of λ.
Q Find the eigen values and eigen vectors of the matrix
In the above example, the algebraic multiplicity of the eigen value −3 is 2 and that of 5 is 1. Corresponding to the eigen value −3, we have two independent eigen vectors and so geometric multiplicity of −3 is 2 and that of the eigen value 5 is one as it has only one eigen vector.
THEOREM 3
Eigen values of the Transpose
The transpose AT of a square matrix A has the same eigen values as A.
Real Matrices with Complex Eigen values and Eigen vectors.
---
### Eigenbases
Eigenvectors of an $n \times n$ matrix $A$ may (or may not!) form a basis for $R^n$. If we are interested in a transformation $y = Ax$, such an
"eigenbasis" (basis of eigen vectors) - if it exists - is of great advantage because then we can represent any x in Rn uniquely as a linear combination of the eigenvectors x1,…,xn, say,
x=c1x1+c2x2+⋯+cnxn
And, denoting the corresponding (not necessarily distinct) eigenvalues of the matrix A by λ1,…,λn, we have Axj=λjxj, so that we simply obtain
This shows that we have decomposed the complicated action of A on an arbitrary vector x into a sum of multiple actions (multiplication by scalars) on the eigenvectors of A.
THEOREM 1
Basis of Eigenvectors.
If an n×n matrix A has n distinct eigenvalues, then A has a basis of eigenvectors x1,…,xn for Rn.
THEOREM 2
Symmetric Matrices.
A symmetric matrix has an orthonormal basis of eigenvectors for Rn.
Similarity of Matrices.
Two matrices A and B are said to be similar if there exists an invertible matrix P such that
P−1AP=B
DEFINITION
Similar Matrices, Similarity Transformation.
An n×n matrix A^ is called similar to an n×n matrix A if A^=P−1AP
for some (non singular!) n×n matrix P. This transformation, which gives A^ from A, is called a similarity transformation.
The key property of this transformation is that it preserves the eigen values of A.
THEOREM 3
Eigen values and Eigen vectors of similar Matrices
If A^ is similar to A, then A^ has the same eigen values as A
Furthermore, if x is an eigenvector of A, then y=P−1x is an eigenvector of A^ corresponding to the same eigen value.
Let,
Then
EXAMPLE
Eigen values and Vectors of similar Matrices.
Let,
Then
detP=1. We see that A^ has the eigen values
λ1=3, λ2=2.
The characteristic equation of A is
(6−λ)(−1−λ)+12=λ2−5λ+6=0
It has the roots (the eigenvalues of A)
λ1=3,λ2=2. confirming the first part of Theorem 3.
We confirm the second part. From the first component of (A−λI)x=0 we have (6−λ)x1−3x2=0.
For λ=3 this gives 3x1−3x2=0, say, x1=[11]T
For λ=2 it gives 4x1−3x2=0, say, x2=[34]T
In theorem 3 we thus have
y1=P−1x1=[4−1−31][11]=[10],
Indeed, these are eigenvectors of the diagonal matrix A^.
Perhaps we see that x1 and x2 are the columns of P. This suggests the general method of transforming a matrix A to diagonal
form D by using P=X, the matrix with eigenvectors as columns.
Diagonalization
Diagonalization is a process by which the given matrix A is reduced to its simplest form (to a diagonal matrix) such that the eigen values are same and both are similar matrices.
THEOREM 4
Diagonalization of a Matrix
If an n×n matrix A has a basis of eigen vectors, then
D=X−1AX
is diagonal, with the eigenvalues of A as the entries on the main diagonal. Here X is the matrix with these eigen vectors as column vectors. Also,
Dm=X−1AmX(m=2,3,…)
General Method.
Now we shall describe a method to diagonalize a given diagonalizable matrix. This method is applicable to n×n matrices having n linearly independent eigen vectors. We explain this method for a 3×3 matrix, and the method can be extended to square matrix of any order.
Consider three independent eigen vectors
corresponding to the eigen values λ1,λ2,λ3
of a 3×3 matrix A=a11a21a31a12a22a32a13a23a33
\begin{bmatrix} 1 & -1 \ 0 & 0 \end{bmatrix} \begin{bmatrix} x \ y \end{bmatrix} = \begin{bmatrix} 0 \ 0 \end{bmatrix}
\begin{aligned}
x - y &= 0 \
x &= y \
x = t, &\quad y = t \
X_2 = \begin{bmatrix} x \ y \end{bmatrix} &= \begin{bmatrix} t \ t \end{bmatrix} = t \begin{bmatrix} 1 \ 1 \end{bmatrix}
\end{aligned}
---
### $\lambda = -1$
\begin{bmatrix} 2 & 2 \ 2 & 2 \end{bmatrix} \begin{bmatrix} x \ y \end{bmatrix} = \begin{bmatrix} 0 \ 0 \end{bmatrix}
$$\qquad R_1 \to \frac{1}{2}R_1$$
\begin{bmatrix} 1 & 1 \ 2 & 2 \end{bmatrix} \begin{bmatrix} x \ y \end{bmatrix} = \begin{bmatrix} 0 \ 0 \end{bmatrix}
$$\qquad R_2 \to R_2 - 2R_1$$
\begin{bmatrix} 1 & 1 \ 0 & 0 \end{bmatrix} \begin{bmatrix} x \ y \end{bmatrix} = \begin{bmatrix} 0 \ 0 \end{bmatrix}
\begin{aligned}
x + y &= 0 \
x &= -y \
x &= t \
y &= -t \
X_1 = \begin{bmatrix} x \ y \end{bmatrix} &= \begin{bmatrix} t \ -t \end{bmatrix} = t \begin{bmatrix} 1 \ -1 \end{bmatrix}
\end{aligned}
Remark : If A is a square matrix with distinct eigenvalues λ1,λ2,…,λn with the corresponding eigenvectors X1,X2,…,Xn then These eigen vectors are linearly independent and hence A is diagonalizable with
Theorem : An n×n square matrix A is diagonalizable if and only if the geometric multiplicity of each eigenvalue equals its algebraic multiplicity.