1.5 Find an Elementary Matrix Solutions

Elementary Matrix

An elementary matrix E is a square matrix that generates an elementary row operation on a matrix A (which need not be square) under the multiplication EA.

From: Linear Algebra (Third Edition) , 2014

E

Fred E. Szabo PhD , in The Linear Algebra Survival Guide, 2015

Elementary Matrix

An elementary matrix is a matrix obtained from an identity matrix by applying one elementary row operation to the identity matrix.

Illustration

■

An elementary matrix resulting from the interchange of two rows

A   =   IdentityMatrix[3]

{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}

A   =   {A_[[1]] , A _[[3]] , A _[[2]] }

{{1, 0, 0}, {0, 0, 1}, {0, 1, 0}}

■

An elementary matrix resulting from multiplication of a row by a nonzero constant

A   =   IdentityMatrix[3]

{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}

A_[[2]]  =   3 A_[[2]];

A

{{1, 0, 0} , {0, 3, 0} , {0, 0, 1}}

■

An elementary matrix resulting from the addition of a multiple of a row to another row

A   =   IdentityMatrix[3]

{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}

A_[[3]]  =   A_[[3]]  −   4 A_[[1]] ;

A

{{1, 0, 0} , {0, 1, 0} , {−   4, 0,1}}

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124095205500126

Additional Applications

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fourth Edition), 2010

Exercises for Section 8.6

1.

For each elementary matrix below, determine its corresponding row operation. Also, use the inverse operation to find the inverse of the given matrix.

⋆(a)

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]$

⋆(b)

$\left[\begin{array}{ccc}1& 0& 0\\ 0& -2& 0\\ 0& 0& 1\end{array}\right]$

(c)

$\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill -4& \hfill 0& \hfill 1\end{array}\right]$

(d)

$\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 6& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]$

⋆(e)

$\left[\begin{array}{rrrr}\hfill 1& \hfill 0& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1& \hfill -2\\ \hfill 0& \hfill 0& \hfill 0& \hfill 1\end{array}\right]$

(f)

$\left[\begin{array}{cccc}0& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\end{array}\right]$

2.

Express each of the following as a product of elementary matrices (if possible), in the manner of Example 5:

⋆(a)

$\left[\begin{array}{cc}4& 9\\ 3& 7\end{array}\right]$

(b)

$\left[\begin{array}{rrr}\hfill -3& \hfill 2& \hfill 1\\ \hfill 13& \hfill -8& \hfill -9\\ \hfill 1& \hfill -1& \hfill 2\end{array}\right]$

⋆(c)

$\left[\begin{array}{rrrr}\hfill 0& \hfill 0& \hfill 5& \hfill 0\\ \hfill -3& \hfill 0& \hfill 0& \hfill -2\\ \hfill 0& \hfill 6& \hfill -10& \hfill -1\\ \hfill 3& \hfill 0& \hfill 0& \hfill 3\end{array}\right]$

3.

Let A and B be m × n matrices. Prove that A and B are row equivalent if and only if B = PA, for some nonsingular m × m matrix P.

4.

Prove that if U is an upper triangular matrix with all main diagonal entries nonzero, then U ⁻¹ exists and is upper triangular. (Hint: Show that the method for calculating the inverse of a matrix does not produce a row of zeroes on the left side of the augmented matrix. Also, show that for each row reduction step, the corresponding elementary matrix is upper triangular. Conclude that U ⁻¹ is the product of upper triangular matrices, and is therefore upper triangular (see Exercise 18(b) in Section 1.5).)

5.

If E is an elementary matrix, show that E ^T is also an elementary matrix. What is the relationship between the row operation corresponding to E and the row operation corresponding to E ^T ?

6.

Let F be an elementary n × n matrix. Show that the product AF ^T is the matrix obtained by performing a "column" operation on A analogous to one of the three types of row operations. (Hint: What is (AF ^T ) ^T ?)

►7.

Prove Corollary 8.9.

8.

Consider the homogeneous system AX = O, where A is an n × n matrix. Show that this system has a nontrivial solution if and only if A cannot be expressed as the product of elementary n × n matrices.

9.

Let A and B be m × n and n × p matrices, respectively, and let E be an m × m elementary matrix.

(a)

Prove that rank(EA) = rank(A).

(b)

Show that if A has k rows of all zeroes, then rank(A) ≤ m − k.

(c)

Show that if A is in reduced row echelon form, then rank(AB) ≤ rank(A). (Use part (b).)

(d)

Use parts (a) and (c) to prove that for a general matrix A, rank(AB) ≤ rank(A).

(e)

Compare this exercise with Exercise 18 in Section 2.3.

⋆10.

True or False:

(a)

Every elementary matrix is square.

(b)

If A and B are row equivalent matrices, then there must be an elementary matrix E such that B = EA.

(c)

If E ₁,…, E _k are n × n elementary matrices, then the inverse of E ₁ E ₂…E _k is E _k …E ₂ E ₁.

(d)

If A is a nonsingular matrix, then A ⁻¹ can be expressed as a product of elementary matrices.

(e)

If R is a row operation, E is its corresponding m × m matrix, and A is any m × n matrix, then the reverse row operation R ⁻¹ has the property R ⁻¹(A) = E ⁻¹ A.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747518000196

Volume 2

A. de Juan , ... R. Tauler , in Comprehensive Chemometrics, 2009

2.19.2.2 Resolution Based on Elementary Matrix Transformations (Gentle)

The resolution method based on elementary matrix transformations proposed by Manne and Grande, ³⁴ hereafter called Gentle, works within the space of raw data and the central idea is that the true solutions C and S ^T can be obtained by matrix transformation from the evolution of any pair of matrices, C _o and S _o ^T, fitting optimally the raw data matrix X. This starting point agrees with the model in Equation (2), where the link between the initial estimates for C _o and S _o ^T and the desired chemically meaningful solutions, C and S ^T, happens via a transformation matrix R.

Thus, this method starts with an initial set of real spectra from the original matrix, S _o ^T, obtained with the use of a pure variable selection method. ¹³ This matrix S _o ^T contains good approximate spectra, which are linear combinations of the true spectra sought. Subsequently, an initial C _o matrix is calculated by least squares from X and S _o ^T. The pair of matrices C _o and S _o ^T obtained in this way reproduces the original data set X with an optimal fit. The matrix C _o is then transformed into the chemically meaningful matrix C via a series of elementary matrix transformation steps that each affects a small part of the data. Thus, the series of successive transformations can be expressed as

(12) ${\mathbf{C}}_1={\mathbf{C}}_{\text{o}}{\mathbf{R}}_{\text{o}},{\mathbf{C}}_2={\mathbf{C}}_1{\mathbf{R}}_1,\dots ,\mathbf{C}={\mathbf{C}}_n{\mathbf{R}}_n$

Or, in a more compact way,

(13) $\mathbf{C}={\mathbf{C}}_{\text{o}}{\mathbf{R}}_{\text{o}}{\mathbf{R}}_1\dots {\mathbf{R}}_n$

To preserve the fit of the original data matrix X, the spectra matrix S _o ^T is successively transformed as

(14) ${\mathbf{S}}^{\text{T}}={\mathbf{R}}_n{}^{-1}\dots {\mathbf{R}}_1{}^{-1}{\mathbf{R}}_{\text{o}}{}^{-1}{\mathbf{S}}_{\text{o}}^{\text{T}}$

If R is defined as R  = R _o R ₁…R _n , we can easily recall the expression in Equation (2). The particularity of this approach lies in the fact that the successive transformation matrices R _o, R ₁, …, R _n are elementary matrices. To understand the way these R _i matrices act on small parts of the concentration profiles and spectra, we reformulate the bilinear CR model in a profilewise way. Let us assume that we have a two-component system. The related CR model, expressed as a sum of the contributions of each dyad of profiles, can be written as

(15) $\mathbf{X}={\mathbf{c}}_1{\mathbf{s}}_1{}^{\text{T}}+{\mathbf{c}}_2{\mathbf{s}}_2{}^{\text{T}}$

Adding and subtracting the term k c ₂ s ₁ ^T to the above expression and reorganizing the terms, we obtain the following two equations:

(16) $\mathbf{X}={\mathbf{c}}_1{\mathbf{s}}_1{}^{\text{T}}+{\mathbf{c}}_2{\mathbf{s}}_2{}^{\text{T}}+\mathcal{k}{\mathbf{c}}_2{\mathbf{s}}_1{}^{\text{T}}-\mathcal{k}{\mathbf{c}}_2{\mathbf{s}}_1{}^{\text{T}}$

(17) $\mathbf{X}=({\mathbf{c}}_1+\mathcal{k}{\mathbf{c}}_2){\mathbf{s}}_1{}^{\text{T}}+{\mathbf{c}}_2({\mathbf{s}}_2{}^{\text{T}}-\mathcal{k}{\mathbf{s}}_1{}^{\text{T}})$

Figure 3 shows the relationship between the original bilinear model in Equation (15) and the transformed one in Equation (17) in matrix form.

Figure 3. Scheme of single-step modification of profiles in a two-component system by elementary matrix transformation.

Figures 3(a) and 3(c) show the original model in Equation (15) and the model in Equation (17), respectively. The link between the two is the transformation matrix R shown in Figure 3(b) . This transformation matrix has the property of having ones along the diagonal and only one nonnull off-diagonal element. Matrices with this structure receive the name of elementary matrices. ³⁵

The elementary matrix in Figure 3(b) is represented by the algebraic notation E ₂₁(k), where the subindex indicates the nonnull element in the data matrix. The inverse of the elementary matrix E ₂₁(k) is E ₂₁(−k). Right multiplication of C by the elementary matrix E ₂₁(k) modifies the first column of C by addition of k times the second profile, that is, c ₁→c ₁+kc ₂, and left multiplication of S ^T by E ₂₁(−k) modifies the second row of S ^T by addition of −k times the first profile, that is, s ₂→s ₂−ks ₁.

Without loss of generality, for a system with n components, an elementary matrix transformation using matrix E _ji (k) would lead to the replacements c _i→c _i+kc _j and s _j→s _j−ks _j. To represent a concentration profile c _i as a linear combination of all of the others in a data set, the product of the elementary matrices Π E _ji (k _j ) will lead to the replacement c _i→c _i+Σk_j c _j. As a consequence, all spectra with j ≠ i would be modified accordingly, as s _j→s _j−k_j s _j.

Figure 3 and the explanations above have helped to visualize the two main ideas linked to elementary matrix transformations. First, the transformed concentration profiles and spectra are linear combinations of the starting profiles. Second, an elementary matrix transformation affects concentration profiles and spectra pairwise, hence the need of successive elementary matrix transformations to obtain a global modification of C and S ^T. The elementary matrix transformations presented are the ones used by the Gentle method to transform the initial concentration and spectra estimates to the real solutions sought in the resolution approach. The strategy used in practice and the conditions that the data set should fulfill to be analyzed are explained below in detail.

The application of the resolution method based on elementary matrix transformations will be shown for the chromatographic system (HPLC-DAD) with four components shown in Figure 1 . Once the number of components in the system is known, the steps given below should be followed:

(a)

Generation of initial spectral estimates, S _o ^T, from the original data matrix X, by pure variable selection methods and normalization to constant area.

(b)

Calculation of C _o by least squares according to the bilinear resolution model, as ${\mathbf{C}}_{\text{o}}=\mathbf{X}{({\mathbf{S}}_{\text{o}}^{\text{T}})}^{+}$ .

(c)

Organization of concentration profiles according to elution order in C _o.

(d)

Application of constraints to the elution profiles via elementary matrix transformations (nonnegativity in the elution profiles and preservation of the correct elution windows).

(e)

Modification of the pure spectra with the inverse of the elementary matrices used in step (d) to provide an optimal reproduction of the original data set.

Step (d) is the core of the algorithm, and highlights the fact that the application of constraints in Gentle differs from the methods used in other iterative approaches. Knowing that elementary matrix transformations produce linear combinations of existing profiles, it seems logical that the shape of a given concentration profile c _i must be basically modified by combination with the closest left c _i−1 and/or right c _i+1 neighboring profiles. Therefore, the elementary matrix transformations to eliminate the negative parts of a given concentration profile c _i follow the sequence given below:

i.

Selection of the profile with the lowest minimum (largest negative contribution) c _i ^(m) where m is the number of the iterative transformation step.

ii.

See whether c _i ^(m) needs to pass through a transformation. This will happen if

(a)

The negative minimum is lower than a preset negative threshold value.

(b)

One of the neighboring profiles, c _i−1 ^(m) or c _i+1 ^(m), is the largest profile above the minimum.

(c)

The largest profile is larger than the preset positive threshold value (the absolute value of the threshold is usually 1% of the absolute maximum in C _o).

iii.

If all conditions in step (ii) are fulfilled, take the largest neighboring profile, for example, c _i−1 ^(m), and replace c _i ^(m) by c _i ^(m+1)  = c _i ^(m)  + k c _i−1 ^(m), where k is chosen so that the lowest minimum in the profile c _i ^(m+1) equals the preset negative threshold value. This is equivalent to performing C _m+1  = C _m E _i,i−1(k).

iv.

Transform accordingly the connected spectral profiles, that is, s _i−1 ^(m+1)  = s _i−1 ^(m) – k s _i ^(m). This is the elementary matrix transformation S ^T _m+1  = E _i,i−1(−k)S ^T _m . (For a better understanding of steps (iii) and (iv), see the matrix C _o and the concentration profiles and related spectra after the first elementary transformation given in Figures 4(a) and 4(b) .)

v.

Normalize the spectra in S ^T _m+1, rescale the profiles in C _m+1 accordingly, and go back to step (ii) until none of the concentration profiles fulfill the conditions to be transformed.

Figure 4. (a) Initial spectra estimates (S _o ^T) and least-squares calculation of C _o. The blue profile is the most negative profile to be transformed. The green profile is used to perform the corrective elementary matrix transformation. (b) Concentration profiles after the first elementary matrix transformation, C ₁. Related transformed spectra matrix, S ₁ ^T. (c) Final solutions of C and S ^T after application of nonnegativity and correction of elution windows.

Once the concentration profiles are positive, it is possible to check whether the inverse transformations keep the related spectra positive. If the factor k is modified in a gradual manner, keeping the value slightly smaller than the exact optimum, this check may be avoided very often.

This is the procedure followed to apply the nonnegativity constraint. After this step, the final solution is obtained modifying the concentration profiles so that they match their predetermined elution windows, that is, minimizing the concentration profile elements outside the preset elution window. The initial setting of these windows is done in an automatic way after the nonnegativity correction, taking the values around the maximum that exceed the preset positive threshold. Once this is done, each concentration profile is modified by a product of elementary matrix transformations that will give

(18) ${\mathbf{c}}_i^{(m)}={\mathbf{c}}_i^{(m-1)}+{\displaystyle \sum _{j\ne i}}{\mathbf{c}}_j^{(m-1)}{\mathcal{k}}_j$

where the k _j elements are calculated by linear regression minimizing the deviation from zero of the elements of c _i ^(m) outside the determined elution window. This calculation slightly modifies the initial elution windows and, in order to obtain more reliable solutions, this procedure is repeated a few times, modifying the definition of the elution windows according to the results of the last iterative cycle. Figure 4(c) shows the final profiles recovered for the data set of Figure 1 by elementary matrix transformations after suitable introduction of all needed constraints.

Quality checks of the results can be done by examining the meaningfulness of the resolved profiles, for example, lack of unimodality could be considered a serious fault and be likely related to a wrong estimation of the number of compounds. In addition, the presence of nonnegative elements in the R matrix is indicative of a successful result. An independent validation of the resolved spectra could be achieved by comparing the spectral shapes recovered with those obtained by subwindow factor analysis (SFA), ³⁶ a resolution method mainly focused on the resolution of pure spectra (see the chapter on noniterative curve resolution methods for further explanation of SFA, Chapter 2.18). Although rotational ambiguity can still exist, if the two methods give the same solution, the results might be very likely correct.

An important point to make is that Gentle is a suitable method for analyzing process data, where concentration profiles evolve in a sequential way and elution windows can be easily determined. Data sets with less structured concentration profiles, such as environmental or spectroscopic images, cannot be easily solved using this approach.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780444527011000508

Matrices

Richard Bronson , ... John T. Saccoman , in Linear Algebra (Third Edition), 2014

Important Terms

augmented matrix

block diagonal matrix

coefficient matrix

cofactor

column matrix

component

consistent equations

derived set

determinant

diagonal element

diagonal matrix

dimension

directed line segment

element

elementary matrix

elementary row operations

equivalent directed line segments

expansion by cofactor

Gaussian elimination

homogeneous equations

identity matrix

inconsistent equations

inverse

invertible matrix

linear equation

lower triangular matrix

LU decomposition

main diagonal

mathematical induction

matrix

nonhomogeneous equations

nonsingular matrix

n-tuple

order

partitioned matrix

pivot

pivotal condersation

power of a matrix

row matrix

row-reduced form

scalar

singular matrix

skew-symmetric matrix

square

submatrix

symmetric matrix

transpose

trivial solution

upper triangular matrix

zero matrix

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123914200000019

The inverse

Richard Bronson , Gabriel B. Costa , in Matrix Methods (Fourth Edition), 2021

3.1 Introduction

Definition 1

An inverse of an n  × n matrix A is an n  × n matrix B having the property that

(1) $\mathbf{A}\mathbf{B}=\mathbf{B}\mathbf{A}=\mathbf{I}\text{.}$

Here, B is called an inverse of A and is usually denoted by A ⁻¹. If a square matrix A has an inverse, it is said to be invertible or nonsingular. If A does not possess an inverse, it is said to be singular. Note that inverses are only defined for square matrices. In particular, the identity matrix is invertible and is its own inverse because

$\mathbf{I}\mathbf{I}=\mathbf{I}\text{.}$

Example 1

Determine whether

$\mathbf{B}=\left[\begin{array}{cc}1& \frac{1}{2}\\ \frac{1}{3}& \frac{1}{4}\end{array}\right]\text{or}\mathbf{C}=\left[\begin{array}{rr}\hfill -2& \hfill 1\\ \hfill \frac{3}{2}& \hfill -\frac{1}{2}\end{array}\right]$

are inverses for

$\mathbf{A}=\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]\text{.}$

Solution B is an inverse if and only if AB   =   BA=  I; C is an inverse if and only if AC   =   CA=  I. Here,

$\mathbf{A}\mathbf{B}=\left[\begin{array}{rr}\hfill 1& \hfill 2\\ \hfill 3& \hfill 4\end{array}\right]\left[\begin{array}{rr}\hfill 1& \hfill \frac{1}{2}\\ \hfill \frac{1}{3}& \hfill \frac{1}{4}\end{array}\right]=\left[\begin{array}{rr}\hfill \frac{5}{3}& \hfill 1\\ \hfill \frac{13}{3}& \hfill \frac{5}{2}\end{array}\right]\ne \left[\begin{array}{rr}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right],$

while

$\mathbf{A}\mathbf{C}=\left[\begin{array}{rr}\hfill 1& \hfill 2\\ \hfill 3& \hfill 4\end{array}\right]\left[\begin{array}{rr}\hfill -2& \hfill 1\\ \hfill \frac{3}{2}& \hfill -\frac{1}{2}\end{array}\right]=\left[\begin{array}{rr}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right]=\left[\begin{array}{rr}\hfill -2& \hfill 1\\ \hfill \frac{3}{2}& \hfill -\frac{1}{2}\end{array}\right]\left[\begin{array}{rr}\hfill 1& \hfill 2\\ \hfill 3& \hfill 4\end{array}\right]=\mathbf{C}\mathbf{A}\text{.}$

Thus, B is not an inverse for A, but C is. We may write A ⁻¹  = C. ■

Definition 1 is a test for checking whether a given matrix is an inverse of another given matrix. In the Final Comments to this chapter we prove that if AB=I for two square matrices of the same order, then A and B commute and BA=I. Thus, we can reduce the checking procedure by half. A matrix B is an inverse for a square matrix A if either AB=I or BA=I; each equality automatically guarantees the other for square matrices. We will show in Section 3.4 that an inverse is unique. If a square matrix has an inverse, it has only one.

Definition 1 does not provide a method for finding inverses. We develop such a procedure in the next section. Still, inverses for some matrices can be found directly.

The inverse for a diagonal matrix D having only nonzero elements on its main diagonal is also a diagonal matrix whose diagonal elements are the reciprocals of the corresponding diagonal elements of D. That is, if

$\mathbf{D}=\left[\begin{array}{ccccc}{\lambda }_1& & & & \mathbf{0}\\ & {\lambda }_2& & & \\ & & {\lambda }_3& & \\ & & & \ddots & \\ \mathbf{0}& & & & {\lambda }_n\end{array}\right],$

then,

${\mathbf{D}}^{-1}=\left[\begin{array}{ccccc}\frac{1}{{\lambda }_1}& & & & \mathbf{0}\\ & \frac{1}{{\lambda }_2}& & & \\ & & \frac{1}{{\lambda }_3}& & \\ & & & \ddots & \\ \mathbf{0}& & & & \frac{1}{{\lambda }_n}\end{array}\right]\text{.}$

It is easy to show that if any diagonal element in a diagonal matrix is zero, then that matrix is singular. (See Problem 57.)

An elementary matrix E is a square matrix that generates an elementary row operation on a matrix A (which need not be square) under the multiplication EA. Elementary matrices are constructed by applying the desired elementary row operation to an identity matrix of appropriate order. The appropriate order for both I and E is a square matrix having as many columns as there are rows in A; then, the multiplication EA is defined. Because identity matrices contain many zeros, the process for constructing elementary matrices can be simplified still further. After all, nothing is accomplished by interchanging the positions of zeros, multiplying zeros by nonzero constants, or adding zeros to zeros.

(i)

To construct an elementary matrix that interchanges the ith row with the jth row, begin with an identity matrix of the appropriate order. First, interchange the unity element in the i  − i position with the zero in the j  − i position and then interchange the unity element in the j  − j position with the zero in the i  − j position.

(ii)

To construct an elementary matrix that multiplies the ith row of a matrix by the nonzero scalar k, replace the unity element in the i  − i position of the identity matrix of appropriate order with the scalar k.

(iii)

To construct an elementary matrix that adds to the jth row of a matrix k times the ith row, replace the zero element in the j  − i position of the identity matrix of appropriate order with the scalar k.

Example 2

Find elementary matrices that when multiplied on the right by any 4   ×   3 matrix A will (a) interchange the second and fourth rows of A, (b) multiply the third row of A by 3, and (c) add to the fourth row of A  −   5 times its second row.

Solution

(a) $\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\\ 0& 1& 0& 0\end{array}\right],$     (b) $\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 3& 0\\ 0& 0& 0& 1\end{array}\right],$     (c) $\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& -5& 0& 1\end{array}\right]\text{.}$ ■

Example 3

Find elementary matrices that when multiplied on the right by any 3   ×   5 matrix A will (a) interchange the first and second rows of A, (b) multiply the third row of A by −0.5, and (c) add to the third row of A −1 times its second row.

Solution

(a) $\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right],$     (b) $\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& -0.5\end{array}\right],$     (c) $\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -1& 1\end{array}\right]\text{.}$ ■

The inverse of an elementary matrix that interchanges two rows is the matrix itself, it is its own inverse. The inverse of an elementary matrix that multiplies one row by a nonzero scalar k is obtained by replacing k by 1/k. The inverse of an elementary matrix that adds to one row a constant k times another row is obtained by replacing the scalar k by −k.

Example 4

Compute the inverses of the elementary matrices found in Example 2.

Solution

(a) $\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\\ 0& 1& 0& 0\end{array}\right],$     (b) $\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& \frac{1}{3}& 0\\ 0& 0& 0& 1\end{array}\right],$     (c) $\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 5& 0& 1\end{array}\right]\text{.}$ ■

Example 5

Compute the inverses of the elementary matrices found in Example 3.

Solution

(a) $\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right],$     (b) $\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& -2\end{array}\right],$     (c) $\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 1\end{array}\right]\text{.}$

Finally, if A can be partitioned into the block diagonal form,

$\mathbf{A}=\left[\begin{array}{ccccc}{\mathbf{A}}_1& & & & \mathbf{0}\\ & {\mathbf{A}}_2& & & \\ & & {\mathbf{A}}_3& & \\ & & & \ddots & \\ \mathbf{0}& & & & {\mathbf{A}}_n\end{array}\right],$

then A is invertible if and only if each of the diagonal blocks A ₁, A ₂, …, A _n is invertible and

${\mathbf{A}}^{-1}=\left[\begin{array}{ccccc}{\mathbf{A}}_1^{-1}& & & & \mathbf{0}\\ & {\mathbf{A}}_2^{-1}& & & \\ & & {\mathbf{A}}_3^{-1}& & \\ & & & \ddots & \\ \mathbf{0}& & & & {\mathbf{A}}_n^{-1}\end{array}\right]\text{.}■$

Example 6

Find the inverse of

$\mathbf{A}=\left[\begin{array}{ccccccc}2& 0& 0& 0& 0& 0& 0\\ 0& 5& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 4& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0\end{array}\right]\text{.}$

Solution Set

$\begin{array}{cccc}{\mathbf{A}}_1=\left[\begin{array}{cc}2& 0\\ 0& 5\end{array}\right],& {\mathbf{A}}_2=\left[\begin{array}{cc}1& 0\\ 4& 1\end{array}\right],& \text{and}& {\mathbf{A}}_3=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right];\end{array}$

then, A is in the block diagonal form

$\mathbf{A}=\left[\begin{array}{ccc}{\mathbf{A}}_1& & 0\\ & {\mathbf{A}}_2& \\ 0& & {\mathbf{A}}_3\end{array}\right]\text{.}$

Here A ₁ is a diagonal matrix with nonzero diagonal elements, A ₂ is an elementary matrix that adds to the second row four times the first row, and A ₃ is an elementary matrix that interchanges the second and third rows; thus,

$\begin{array}{cccc}{\mathbf{A}}_1^{-1}=\left[\begin{array}{cc}\frac{1}{2}& 0\\ 0& \frac{1}{5}\end{array}\right],& {\mathbf{A}}_2^{-1}=\left[\begin{array}{cc}1& 0\\ -4& 1\end{array}\right],& \text{and}& {\mathbf{A}}_3^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right],\end{array}$

and

${\mathbf{A}}^{-1}=\left[\begin{array}{ccccccc}\frac{1}{2}& 0& 0& 0& 0& 0& 0\\ 0& \frac{1}{5}& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0\\ 0& 0& -4& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0\end{array}\right]\text{.}■$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128184196000034

Linear Transformations from a Geometric Viewpoint

J. Douglas Carroll , Paul E. Green , in Mathematical Tools for Applied Multivariate Analysis, 1997

4.7.1 Elementary Operations

Elementary operations play an essential role in the solution of sets of simultaneous equations. Illustratively taking the case of the rows of a transformation matrix, there are three basic operations–called elementary row operations–that can be used to transform one matrix into another. We may

1.

interchange any two rows;

2.

multiply any row by a nonzero scalar;

3.

add to any given row a scalar multiple of some other row.

If we change some matrix A into another matrix B by the use of elementary row operations, we say that B is row equivalent to A.

Elementary row operations involve the multiplication of A by special kinds of matrices that effect the above transformations. However, we could just as easily talk about elementary column operations–the same kinds as these shown above–that are applied to the columns of A. A matrix so transformed would be called column equivalent to the original matrix. To simplify our discussion, we illustrate the ideas via elementary row operations. The reader should bear in mind, however, that the same approach is applicable to the columns of A.

To illustrate how elementary row operations can be applied to the general problem of solving a set of simultaneous equations, let us again consider the two equations described earlier:

$\text{I}\{\begin{array}{r}4x_1-10x_2=-2\hfill \\ 3x_1+7x_2=13\hfill \end{array}$

Suppose we first multiply all members of the first equation by $-\frac{3}{4}$ and then add the result to those of the second equation:

$\text{II}\{\begin{array}{c}4x_1-10x_2=-2\hfill \\ \hfill \frac{29}{2}{x}_2=\frac{29}{2}\end{array}$

Next, let us multiply the second equation by $\frac{2}{29}$ . If so, we obtain

$\text{III}\{\begin{array}{c}4x_1-10x_2=-2\\ \hfill x_2=1\end{array}$

All these sets of equations are row equivalent in the sense that all three sets have the same solution:

$\begin{array}{c}{x}_1=2\\ x_2=1\end{array}$

and each can be transformed to either of the others via elementary row operations. However, it is clear that the solution to the third set of equations is most apparent and easily found.

While elementary row operations are useful in the general task of solving sets of simultaneous equations, this is not their only desirable feature. A second, and major, attraction is the fact that elementary operations (row or column), as applied to a matrix A, do not change its rank. Moreover, as will be shown, elementary operations transform the given matrix in such a way as to make its rank easy to determine by inspection. As it turns out, all three sets of equations above have the same rank (rank 2) since they are all equivalent in terms of elementary row operations.

Elementary row operations are performed by a special set of square, nonsingular matrices called elementary matrices. An elementary matrix is a nonsingular matrix that can be obtained from the identity matrix by an elementary row operation. For example, if we wanted to interchange two rows of a matrix, we could do so by means of the permutation matrix

$\left[\begin{array}{ll}0\hfill & 1\hfill \\ 1\hfill & 0\hfill \end{array}\right]$

For example, if we have the point $\text{x}=\left[\begin{array}{l}1\\ 2\end{array}\right]$ in two dimensions, the premultiplication of x by the permutation matrix above would yield: ¹¹

${\text{x}}^{*}=\left[\begin{array}{ll}0\hfill & 1\hfill \\ 1\hfill & 0\hfill \end{array}\right]\left[\begin{array}{l}1\\ 2\end{array}\right]=\left[\begin{array}{l}2\\ 1\end{array}\right]$

We note that the coordinates of x have, indeed, been permuted.

As mentioned above, elementary matrices are nonsingular. In the 2 × 2 matrix case, the set of elementary matrices consists of the following:

I.

Permutation

$\left[\begin{array}{ll}0\hfill & 1\hfill \\ 1\hfill & 0\hfill \end{array}\right]$

II.

Stretches

$\begin{array}{llll}\left[\begin{array}{ll}k\hfill & 0\hfill \\ 0\hfill & 1\hfill \end{array}\right]\hfill & \begin{array}{l}\text{A\hspace{0.17em}stretch\hspace{0.17em}or\hspace{0.17em}compression}\\ \text{of\hspace{0.17em}the\hspace{0.17em}plane\hspace{0.17em}that\hspace{0.17em}is}\\ \text{parallel\hspace{0.17em}to\hspace{0.17em}the}x\text{\hspace{0.17em}axis;}\end{array}\hfill & \left[\begin{array}{ll}1\hfill & 0\hfill \\ 0\hfill & k\hfill \end{array}\right]\hfill & \begin{array}{l}\text{A\hspace{0.17em}stretch\hspace{0.17em}or\hspace{0.17em}compression}\\ \text{of\hspace{0.17em}the\hspace{0.17em}plane\hspace{0.17em}that\hspace{0.17em}is}\\ \text{parallel\hspace{0.17em}to\hspace{0.17em}the}y\text{\hspace{0.17em}axis}\end{array}\hfill \end{array}$

III.

Shears

$\begin{array}{llll}\left[\begin{array}{ll}1\hfill & c\hfill \\ 0\hfill & 1\hfill \end{array}\right]\hfill & \begin{array}{l}\text{A\hspace{0.17em}shear\hspace{0.17em}parallel\hspace{0.17em}to}\\ \text{the}x\text{\hspace{0.17em}axis;}\end{array}\hfill & \left[\begin{array}{ll}1\hfill & 0\hfill \\ c\hfill & 1\hfill \end{array}\right]\hfill & \begin{array}{l}\text{A\hspace{0.17em}shear\hspace{0.17em}parallel\hspace{0.17em}to}\\ \text{the}y\text{\hspace{0.17em}axis}\end{array}\hfill \end{array}$

Continuing with the numerical example involving $\text{x}=\left[\begin{array}{l}1\\ 2\end{array}\right]$ , we have

Stretches

$\begin{array}{ll}\left[\begin{array}{ll}k\hfill & 0\hfill \\ 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{l}1\\ 2\end{array}\right]=\left[\begin{array}{l}k\\ 2\end{array}\right];\hfill & \left[\begin{array}{ll}1\hfill & 0\hfill \\ 0\hfill & k\hfill \end{array}\right]\left[\begin{array}{l}1\\ 2\end{array}\right]=\hfill \end{array}\left[\begin{array}{l}1\\ 2k\end{array}\right]$

Shears

$\begin{array}{ll}\left[\begin{array}{ll}1\hfill & c\hfill \\ 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{l}1\\ 2\end{array}\right]=\left[\begin{array}{l}1+2c\\ 2\end{array}\right];\hfill & \left[\begin{array}{ll}1\hfill & 0\hfill \\ c\hfill & 1\hfill \end{array}\right]\left[\begin{array}{l}1\\ 2\end{array}\right]=\hfill \end{array}\left[\begin{array}{l}1\\ c+2\end{array}\right]$

But, there is nothing stopping us from applying, in some prescribed order, a series of premultiplications by elementary matrices. Furthermore, the product of a set of nonsingular matrices will itself be nonsingular.

The geometric character of permutations, stretches, and shears has already been illustrated in Section 4.5. Here we are interested in two major applications of elementary row operations and the matrices that represent them:

1.

determining the rank of a matrix, and

2.

finding the inverse of a matrix, when such inverse exists. Each application is described in turn.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780121609542500056

Numerical Analysis

John N. Shoosmith , in Encyclopedia of Physical Science and Technology (Third Edition), 2003

V.C Nonsymmetric Matrices

The problem of finding the eigenvalues of a nonsymmetric matrix is inherently less stable than the symmetric case; furthermore, some or all of the eigenvalues and eigenvectors may be complex.

The first stage is to "balance" the matrix by applying similarity tranformations in order to make the maximum element in corresponding rows and columns approximately equal. Next, the matrix is reduced to "Hessenburg form" by applying stablilized elementary similarity transformations. An upper Hessenburg matrix has the form

$\text{H}=\left[\begin{array}{lllll}{\text{a}}_{1,1}& {\text{a}}_{1,2}& {\text{a}}_{1,3}& \cdot \cdot \cdot & {\text{a}}_{1,\text{n}}\\ {\text{a}}_{2,1}& {\text{a}}_{2,2}& {\text{a}}_{2,3}& \cdot \cdot \cdot & {\text{a}}_{2,\text{n}}\\ 0& {\text{a}}_{3,2}& {\text{a}}_{3,3}& \cdot \cdot \cdot & {\text{a}}_{3,\text{n}}\\ 0& 0& {\text{a}}_{4,3}& \cdot \cdot \cdot & {\text{a}}_{4,\text{n}}\\ \cdot & & & \cdot \cdot \cdot & \cdot \\ \cdot & & & \cdot \cdot \cdot & \cdot \\ \cdot & & & \cdot \cdot \cdot & \cdot \\ 0& 0& 0& \cdot \cdot \cdot {\text{a}}_{\text{n},\text{n}-1}& {\text{a}}_{\text{n},\text{n}}\end{array}\right]$

The elementary matrices are similar in form to those used in the LU factorization (Gaussian elimination) process, except that the pivotal element is taken to be one element below the diagonal. As in LU factorization for general matrices, the rows are interchanged to maximize the pivotal element; however, a difference is that for each elementary matrix multiplying A on the left, its inverse is multiplied on the right, and each row interchange is accompanied by the corresponding column interchange, in order to preserve the eigenvalues.

Since real nonsymmetric matrices may have complex conjugate pairs of eigenvalues, an application of the QR algorithm with origin shift as described for symmetric matrices will involve computing with complex numbers. To avoid this, the double-shift QR algorithm is usually applied to the Hessenburg matrix H ⁽⁰⁾ obtained in the first stage. The kth iteration of this method is

$\begin{array}{ll}({\text{H}}^{(\text{k})}-{\sigma }_{\text{k},1}\text{I})({\text{H}}^{(\text{k})}-& {\sigma }_{\sigma \text{k},2}\text{I})={\text{Q}}^{(\text{k})}{\text{R}}^{(\text{k})}\\ & {\text{H}}^{(\text{k}+1)}={\text{Q}}^{(\text{k})\text{T}}{\text{H}}^{(\text{k})}{\text{Q}}^{(\text{k})}\end{array}$

The shifts σ _{k, 1} and σ _{k, 2} are taken to be the eigenvalues of the lowest 2   ×   2 submatrix of H ^(k); however, when convergence of this submatrix is ascertained, the method is applied to the remaining upper submatrix in the same way. Eventually the sequence H ^(k), k  =   0, 1, 2, …, will converge to a triangular matrix, except that there will be 2   ×   2 blocks on the diagonal for each pair of complex eigenvalues.

As before, the transformations may be accumulated if all of the eigenvectors are required. If the eigenvector associated with a specific eigenvalue is required, inverse iteration may be used (albeit with complex arithmetic if the eigenvalue is complex).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B0122274105005056

SOLUTION OF EQUATIONS

M.V.K. Chari , S.J. Salon , in Numerical Methods in Electromagnetism, 2000

The LDL^T Decomposition

If A is symmetric, then the decomposition can be made in the more convenient form A = LDL^T , where L is unit lower triangular and D is a diagonal matrix. We see this as follows: We have shown that A can be expressed as A = LDU′. In this case A = A^T = (LDU′) ^T = U′ ^T D ^T L ^T . Here U′ ^T is unit lower triangular, D^T is diagonal, and L^T is upper triangular. As U^TD^TL^T is a decomposition of A and this decomposition is unique, we deduce that U′ ^T = L^T . If A is positive definite, then the elements of D are positive.

We will now show that Gauss elimination, triangular factorization, and LU decomposition involve the same operations. We will use the following example [125]:

(11.38) $\begin{array}{r}2x_1+x_2+3x_3=6\\ 2x_1+3x_2+4x_3=9\\ 3x_1+4x_2+7x_3=14\end{array}$

In matrix notation

(11.39) $A=\left(\begin{array}{ccc}2& 1& 3\\ 2& 3& 4\\ 3& 4& 7\end{array}\right)$

Each step of the Gaussian elimination procedure is what we have defined as an elementary row operation. Each corresponds to the premultiplication of A by an elementary matrix. We can therefore express the Gaussian elimination as follows:

(11.40) $\begin{array}{r}\left[\begin{array}{ccc}1& -1/2& -3/2\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& -1/2\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 4/5\end{array}\right]\\ \times \left[\begin{array}{ccc}1& 0& 0\\ 0& 1/2& 0\\ 0& -5/4& 1\end{array}\right]\left[\begin{array}{ccc}1/2& 0& 0\\ -1& 1& 0\\ -3/2& 0& 1\end{array}\right]\left[\begin{array}{ccc}2& 1& 3\\ 2& 3& 4\\ 3& 4& 7\end{array}\right]\end{array}$

This procedure will transform the original matrix into an identity matrix. Consider the last two matrices. Premultiplying the original matrix by the row vector [1/2, 0, 0] divides the first row by 2, thus putting a 1 in the (1,1) place. Premultiplying by [-1, 1, 0] subtracts the second row from the first, putting a 0 in the (2,1) position. Premultiplying by the third row, [-3/2, 0, 1], puts a zero in the (3,1) place. The reader can confirm that the process results in the identity matrix. Note that all of the elementary matrices are triangular, that is,

(11.41) $U_1{U}_2{L}_3{L}_2{L}_{1}A=I$

Because the product of upper (lower) triangular matrices is an upper (lower) triangular matrix, we can write

(11.42) $U_{\pi }{L}_{\pi }A=I$

Here the subscript π is used to indicate a product of matrices. It is also true that the inverse of an upper (lower) triangular matrix is an upper (lower) triangular matrix. Therefore

(11.43) $A=LU,L=L_{\pi }^{-1},U=U_{\pi }^{-1}$

The solution by Gauss elimination involves two stages: (1.) forward elimination (premultiplication by L _π) brings the system into an upper triangular form (U = L_π A) and (2.) back-substitution (premultiplication by U _π) transforms the system into an identity matrix (I = U_πL_πA).

Returning to Ax = y,

(11.44) $\begin{array}{cc}\hfill Ax=y& Ax=y\hfill \\ \hfill & \hfill \\ \hfill L_{\pi }Ax=L_{\pi }y& A=Lu\hfill \\ \hfill Ux=z& Lz=y\hfill \\ \hfill U_{\pi }{U}_x=z& Lz=y\hfill \\ \hfill x=U^{-1}z& Ux=z\hfill \\ \hfill \text{Gauss\hspace{0.17em}elimination}& LU\text{dcomposition}\hfill \end{array}$

Therefore the two methods are equivalent.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780126157604500122

I

Fred E. Szabo PhD , in The Linear Algebra Survival Guide, 2015

Illustration

■

An invertible 2-by-2 matrix

MatrixForm[A1   =   {{1, 2}, {3, 4}}]

$\left(\begin{array}{cc}\hfill \mathtt{1}\hfill & \hfill \mathtt{2}\hfill \\ \hfill \mathtt{3}\hfill & \hfill \mathtt{4}\hfill \end{array}\right)$

MatrixForm [A2   =   Inverse[A1]]

$\left(\begin{array}{cc}\hfill \mathtt{1}\hfill & \hfill \mathtt{2}\hfill \\ \hfill \mathtt{3}\hfill & \hfill \mathtt{4}\hfill \end{array}\right)$

$\left(\begin{array}{cc}\hfill \mathtt{-}\mathtt{2}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \frac{\mathtt{3}}{\mathtt{2}}\hfill & \hfill \mathtt{-}\frac{\mathtt{1}}{\mathtt{2}}\hfill \end{array}\right)$

A1.A2 == IdentityMatrix [2] == A2.A1

True

■

Invertible 2-by-2 elementary matrices

$\mathtt{E}\mathtt{A}\mathtt{1}\mathtt{=}\left(\begin{array}{cc}\hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill \end{array}\right)\left(\mathtt{interchange}\mathtt{of}\mathtt{rows}\mathtt{1}\mathtt{and}\mathtt{2}\right)$

$\mathtt{E}\mathtt{A}\mathtt{2}\mathtt{=}\left(\begin{array}{cc}\hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{s}\hfill \end{array}\right)\left(\mathtt{multiplication}\mathtt{of}\mathtt{row}\mathtt{2}\mathtt{b}\mathtt{y}\mathtt{a}\mathtt{nonzero}\mathtt{constant}\mathtt{s}\right)$

$\mathtt{E}\mathtt{A}\mathtt{3}\mathtt{=}\left(\begin{array}{cc}\hfill \mathtt{s}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \end{array}\right)\left(\mathtt{multiplcation}\mathtt{of}\mathtt{row}\mathtt{1}\mathtt{b}\mathtt{y}\mathtt{a}\mathtt{nonzero}\mathtt{constant}\mathtt{s}\right)$

$\mathtt{E}\mathtt{A}\mathtt{4}\mathtt{=}\left(\begin{array}{cc}\hfill \mathtt{1}\hfill & \hfill \mathtt{s}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \end{array}\right)\left(\mathtt{addition}\mathtt{of}\mathtt{s}\mathtt{times}\mathtt{row}\mathtt{2}\mathtt{t}\mathtt{o}\mathtt{row}\mathtt{1}\right)$

$\mathtt{E}\mathtt{A}\mathtt{5}\mathtt{=}\left(\begin{array}{cc}\hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{s}\hfill & \hfill \mathtt{1}\hfill \end{array}\right)\left(\mathtt{addition}\mathtt{of}\mathtt{s}\mathtt{times}\mathtt{row}\mathtt{1}\mathtt{t}\mathtt{o}\mathtt{row}\mathtt{2}\right)$

■

Invertible 3-by-3 matrices

$\mathsf{A}=\left(\begin{array}{ccc}\hfill \mathsf{9}\hfill & \hfill \mathsf{3}\hfill & \hfill \mathsf{1}\hfill \\ \hfill ‐\mathsf{1}\hfill & \hfill \mathsf{3}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{4}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{9}\hfill \end{array}\right)\text{;}$

Adding 9 times the second row to the first row

$\mathsf{E}\mathsf{1}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{9}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm [A2   =   E1. A]

$\left(\begin{array}{ccc}\hfill \mathtt{0}\hfill & \hfill \mathtt{30}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \mathtt{-}\mathtt{1}\hfill & \hfill \mathtt{3}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{4}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{9}\hfill \end{array}\right)$

Adding 4 times the second row to the third row

$\mathsf{E}\mathsf{2}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{4}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm [A3   =   E2. A2]

$\left(\begin{array}{ccc}\hfill \mathtt{0}\hfill & \hfill \mathtt{30}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \mathtt{-}\mathtt{1}\hfill & \hfill \mathtt{30}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{12}\hfill & \hfill \mathtt{9}\hfill \end{array}\right)$

Interchanging the first and second rows

${\mathsf{E}}_{\mathsf{3}}=\left(\begin{array}{ccc}\hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm [A4   =   E3. A3]

$\left(\begin{array}{ccc}\hfill \mathtt{-}\mathtt{1}\hfill & \hfill \mathtt{3}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{30}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{12}\hfill & \hfill \mathtt{9}\hfill \end{array}\right)$

Multiplying the first row by −   1

$\mathsf{E}\mathsf{4}=\left(\begin{array}{ccc}\hfill ‐\mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm[A5   =   E4. A4]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{-}\mathtt{3}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{30}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{12}\hfill & \hfill \mathtt{9}\hfill \end{array}\right)$

Dividing the second row by 30

$\mathsf{E}\mathsf{5}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}/\mathsf{30}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm[A6   =   E5. A5]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{-}\mathtt{3}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \frac{\mathtt{1}}{\mathtt{30}}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{12}\hfill & \hfill \mathtt{9}\hfill \end{array}\right)$

Subtracting 12 times the second row from the third row

$\mathsf{E}\mathsf{6}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill ‐\mathsf{12}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm[A7   =   E6. A6]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{-}\mathtt{3}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \frac{\mathtt{1}}{\mathtt{30}}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \frac{\mathtt{43}}{\mathtt{5}}\hfill \end{array}\right)$

Adding 3 times the second row to the first row

$\mathsf{E}\mathsf{7}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{3}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm [A8   =   E7. A7 ]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill & \hfill \frac{\mathtt{1}}{\mathtt{10}}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \frac{\mathtt{1}}{\mathtt{30}}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \frac{\mathtt{43}}{\mathtt{5}}\hfill \end{array}\right)$

Multiplying the third row by 5/43

$\mathsf{E}\mathsf{8}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{5}/\mathsf{43}\hfill \end{array}\right)\text{;}$

MatrixForm[A9   =   E8. A8]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill & \hfill \frac{\mathtt{1}}{\mathtt{10}}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \frac{\mathtt{1}}{\mathtt{30}}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \end{array}\right)$

Subtracting 1/30 times the third row from the second row

$\mathsf{E}\mathsf{9}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill ‐\mathsf{1}/\mathsf{30}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm[A10   =   E9. A9]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill & \hfill \frac{\mathtt{1}}{\mathtt{10}}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \end{array}\right)$

Subtracting 1/10 times the third row from the second row

$\mathsf{E}\mathsf{10}=\left(\begin{array}{ccc}\hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill & \hfill ‐\mathsf{1}/\mathsf{10}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{0}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill \end{array}\right)\text{;}$

MatrixForm[A11   =   E10. A10]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \end{array}\right)$

The product of the ten elementary matrices used to convert the matrix A to the 3-by-3 identity matrix is the inverse B matrix of the matrix A.

B   =   E10.E9.E8.E7.E6.E5.E4.E3.E2.E1 == Inverse[A]

True

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124095205500163

Review of Linear Algebra (Optional)

Bernard Kolman , Robert E. Beck , in Elementary Linear Programming with Applications (Second Edition), 1995

0.3 THE INVERSE OF A MATRIX

In this section we restrict our attention to square matrices.

DEFINITION.

An n × n matrix A is called nonsingular or invertible if there exists an n × n matrix B such that

AB −BA = I_n

The matrix B is called the inverse of A. If no such matrix B exists, then A is called singular or noninvertible. If the inverse of A exists, we shall write it as A ⁻¹. Thus

AA⁻¹= A⁻¹A = I_n

EXAMPLE 1.

Let

$A=\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]\text{and}\text{B}=\left[\begin{array}{cc}-2& 1\\ \frac{3}{2}& -\frac{1}{2}\end{array}\right]$

Since

AB = BA = I₂

it follows that B is the inverse of A or B = A ⁻¹ and that A is nonsingular.

EXAMPLE 2.

Let

$\text{A}=\left[\begin{array}{cc}1& 3\\ 2& 6\end{array}\right]$

Does A have an inverse? If it does, let such an inverse be denoted by

$\text{B}=\left[\begin{array}{cc}x& y\\ z& w\end{array}\right]$

Then

$AB=\left[\begin{array}{cc}1& 3\\ 2& 6\end{array}\right]\left[\begin{array}{cc}x& y\\ z& w\end{array}\right]=I_2=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$

Thus,

$\left[\begin{array}{cc}x+3z& y+3w\\ 2x+6z& 2y+6w\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],$

which means that we must have

x + 3z =1

2x + 6z =0

Since this linear system has no solution, we conclude that A has no inverse.

In practice, if the matrix B is proposed as the inverse of A, we need only check that AB = I _n because it can be shown that if AB = I _n , then also BA = I _n .

THEOREM 0.3.

(PROPERTIES OF INVERSE).

(a)

If A is nonsingular, then A ⁻¹ is nonsingular and

(A⁻¹)⁻¹= A.

(b)

If A and B are nonsingular, then AB is nonsingular and

(AB)⁻¹=B⁻¹A⁻¹(note that the order changes).

(c)

If A is nonsingular, then A ^T is nonsingular and

(A^T)⁻¹=(A⁻¹)^T.

We now develop some results that will yield a practical method for computing the inverse of a matrix. The method is based on the properties of elementary matrices, which we discuss next.

DEFINITION.

An n × n elementary matrix of type I, type II, or type III is a matrix obtained from the identity matrix I _n by performing a single elementary row operation of type I, type II, or type III, respectively.

EXAMPLE 3.

Matrices E ₁, E ₂, and E ₃ as defined below are elementary matrices.

$E_1=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]The\sec ╡ondandthirdrowswere\mathrm{int}╡erchanged.$

$E_2=\left[\begin{array}{ccc}-3& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]Thefirstrowwasmultipliedby-3$

$E_3=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -4& 0& 1\end{array}\right]-4timesthefirstrowwasaddedtothethirdrow.$

THEOREM 0.4.

Let A be an m × n matrix, and let the matrix B be obtained from A by performing an elementary row operation on A. Let E be the elementary matrix obtained by performing the same elementary row operation on I _n as that performed on A. Then B = EA.

EXAMPLE 4.

Let

$A=\left[\begin{array}{cccc}1& 2& -1& 3\\ 2& 3& 5& 4\\ -3& 2& 4& -2\end{array}\right]$

If we add − 2 times row 1 to row 2, we obtain

$B=\left[\begin{array}{cccc}1& 2& -1& 3\\ 0& -1& 7& -2\\ -3& 2& 4& -2\end{array}\right]$

Performing the same elementary row operation on I ₃, we obtain the elementary matrix

$E=\left[\begin{array}{ccc}1& 0& 0\\ -2& 0& 0\\ 0& 0& 1\end{array}\right]$

It is now easy to verify that B = EA.

The following theorem follows easily from the definition of row equivalence of matrices and Theorem 0.3

THEOREM 0.5.

The m × n matrices A and B are row equivalent if and only if

B=E_kE_k−1…E₂E₁A,

where E ₁, E ₂, …, E _k . are elementary matrices.

THEOREM 0.6.

An elementary matrix is nonsingular and its inverse is an elementary matrix of the same type.

THEOREM 0.7.

An n × n matrix A is nonsingular if and only if A is a product of elementary matrices.

COROLLARY 0.1.

An n × n matrix A is nonsingular if and only if A is row equivalent to I _n .

Suppose now that A is nonsingular. Then, by Corollary 0.1 and Theorem 0.5, there exist elementary matrices E ₁, E ₂, …, E _k such that

I _n =E _k E _k−1…E₂E₁A.

Procedure for Computing A⁻¹

We now have an effective algorithm for computing A ⁻¹. We use elementary row operations to transform A to I _n ; the product of the elementary matrices E _k E _k−1 … E ₂ E ₁ gives A ⁻¹. The algorithm can be efficiently organized as follows. Form the n × 2n matrix [A | I _n ] and perform elementary row operations to transform this matrix to [I _n | A ⁻¹]. Every elementary row operation that is performed on a row of A is also performed on the corresponding row of I _n .

EXAMPLE 5.

Let

$\text{A}=\left[\begin{array}{ccc}1& 1& 2\\ 0& 2& 5\\ 3& 2& 2\end{array}\right].$

Then

$\left[\text{A}|{\text{I}}_3\right]=\left[\begin{array}{ccccccc}1& 1& 2& |& 1& 0& 0\\ 0& 2& 5& |& 0& 1& 0\\ 3& 2& 2& |& 0& 0& 1\end{array}\right]$

Thus,

$\begin{array}{l}\left[\begin{array}{ccccccc}1& 1& 2& |& 1& 0& 0\\ 0& 2& 5& |& 0& 1& 0\\ 3& 2& 2& |& 0& 0& 1\end{array}\right].Add-3timesthefirstrowtothethirdrow,obtaining\\ \left[\begin{array}{ccccccc}1& 1& 2& |& 1& 0& 0\\ 0& 2& 5& |& 0& 1& 0\\ 0& -1& -4& |& -3& 0& 1\end{array}\right].Multiplythe\sec ╡ondrowby\frac{1}{2},obtaining\\ \left[\begin{array}{ccccccc}1& 1& 2& |& 1& 0& 0\\ 0& 1& \frac{5}{2}& |& 0& \frac{1}{2}& 0\\ 0& -1& -4& |& -3& 0& 1\end{array}\right].Addthe\sec ╡ondrowtothethirdrow,obtaining\\ \left[\begin{array}{ccccccc}1& 1& 2& |& 1& 0& 0\\ 0& 1& \frac{5}{2}& |& 0& \frac{1}{2}& 0\\ 0& 0& -\frac{3}{2}& |& -3& \frac{1}{2}& 1\end{array}\right].Multiplythethirdrowby-\frac{2}{3},obtaining\\ \left[\begin{array}{ccccccc}1& 1& 2& |& 1& 0& 0\\ 0& 1& \frac{5}{2}& |& 0& \frac{1}{2}& 0\\ 0& 0& 1& |& 2& -\frac{1}{3}& -\frac{2}{3}\end{array}\right].Add-1timesthe\sec ╡ondrowtothefirstrow,obtaining\\ \left[\begin{array}{ccccccc}1& 0& -\frac{1}{2}& |& 1& -\frac{1}{2}& 0\\ 0& 1& \frac{5}{2}& |& 0& \frac{1}{2}& 0\\ 0& 0& 1& |& 2& -\frac{1}{3}& -\frac{2}{3}\end{array}\right].Add-\frac{5}{2}timesthethirdrowtothe\sec ╡ondrow,obtaining\\ \left[\begin{array}{ccccccc}1& 0& -\frac{1}{2}& |& 1& -\frac{1}{2}& 0\\ 0& 1& 0& |& -5& \frac{4}{3}& \frac{5}{3}\\ 0& 0& 1& |& 2& -\frac{1}{3}& -\frac{2}{3}\end{array}\right].Add\frac{1}{2}timesthethirdrowtothefirstrow,obtaining\\ \left[\begin{array}{ccccccc}1& 0& 0& |& 2& -\frac{2}{3}& -\frac{1}{3}\\ 0& 1& 0& |& -5& \frac{4}{3}& \frac{5}{3}\\ 0& 0& 1& |& 2& -\frac{1}{3}& -\frac{2}{3}\end{array}\right].\end{array}$

Hence,

${\text{A}}^{-1}=\left[\begin{array}{ccc}2& -\frac{2}{3}& -\frac{1}{3}\\ -5& \frac{4}{3}& \frac{5}{3}\\ 2& -\frac{1}{3}& -\frac{2}{3}\end{array}\right]$

It can be shown that if the matrix C in reduced row echelon form obtained from A has a row of zeros, then A is singular. However, observe that once a matrix obtained from A by this process has a row of zeros, then the final matrix C in reduced row echelon form will also have a row of zeros. Thus, we can stop our calculations as soon as we get a matrix from A with a row of zeros and conclude that A ⁻¹ does not exist.

EXAMPLE 6.

Let

$A=\left[\begin{array}{ccc}1& 2& 1\\ 2& 3& -4\\ 1& 3& 7\end{array}\right]$

To find A ⁻¹ we proceed as above:

$\begin{array}{l}\left[\begin{array}{ccccccc}1& 2& 1& |& 1& 0& 0\\ 2& 3& -4& |& 0& 1& 0\\ 1& 3& 7& |& 0& 0& 1\end{array}\right].Add-2timesthefirstrowtothe\sec ╡ondrow,obtaining\\ \left[\begin{array}{ccccccc}1& 2& 1& |& 1& 0& 0\\ 0& -1& -6& |& -2& 1& 0\\ 1& 3& 7& |& 0& 0& 1\end{array}\right].Add-1timesthefirstrowtothethirdrow,obtaining\\ \left[\begin{array}{ccccccc}1& 2& 1& |& 1& 0& 0\\ 0& -1& -6& |& -2& 1& 0\\ 0& 1& 6& |& -1& 0& 1\end{array}\right].Addthe\sec ╡ondrowtothethirdrow,optaining\\ \left[\begin{array}{ccccccc}1& 2& 1& |& 1& 0& 0\\ 0& -1& -6& |& -2& 1& 0\\ 0& 0& 0& |& -3& 1& 1\end{array}\right].\end{array}$

Since we have a matrix with a row of zeros under A, we stop and conclude that A is singular.

The method just presented for calculating A ⁻¹ has the nice feature that we do not have to know, in advance, whether or not A ⁻¹ exists. That is, we set out to find A ⁻¹, and we either find it or determine that it does not exist.

Suppose now that A is an n × n matrix, and consider the linear system

(1) $Ax=b$

If A is nonsingular, then A ⁻¹ exists. Multiplying both sides of (1) by A ⁻¹ on the left, we have

A⁻¹Ax=A⁻¹b

Thus, if A ⁻¹ is known, then the solution to (1) can be simply calculated as A ⁻¹ b.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124179103500036

1.5 Find an Elementary Matrix Solutions

Source: https://www.sciencedirect.com/topics/mathematics/elementary-matrix

Share :