[ RubyAlg ] MIT Linear Algebra, Spring 2005 - Lec2

Source From Here
Elimination Process
Consider we have system equations as below:


Actually, we can treat it as a matrix multiplication: Ax=b


Then we can use Gaussian elimination to help use solve the equations: A=LU

To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations: 1) Swapping two rows, 2) Multiplying a row by a non-zero number, 3) Adding a multiple of one row to another row. Using these operations, a matrix can always be transformed into an upper triangular matrix, and in fact one that is in row echelon form.

1. Row1*-3 + Row2 to have Row2=[0,2,-2]
2. Row2*-2 + Row3 to have Row3=[0,0,5]
3. Have a successful elimination:

Augmented Matrix
In linear algebra, an augmented matrix is a matrix obtained by appending the columns of two given matrices, usually for the purpose of performing the same elementary row operations on each of the given matrices. Take upper equation as example:


Then let's change back to our system equations:


Matrix Multiplication 
For matrix multiplication, we can use different view point to do the calculation.

Matrix * Column : Column Combination of Matrix
Matrix multiple Column will produce a Column which is the combination of each column of Matrix. For example:


Let's use code to test this concept:

>> m = LA.newMtx3(3,3,[1,2,3,4,5,6,7,8,9])
=> #
>> c = LA.newMtx3(3,1,[1,2,3])
=> #
>> m*c # Matrix x Column = Column
=> # # 3x1 matrix
>> m.col2Mtx(0)+m.col2Mtx(1)*2+m.col2Mtx(2)*3
=> # # Same result as m*b

Row * Matrix = Row : Row Combination of Matrix
Row multiple Matrix will produce Row which is the row combination of Matrix (1xN * NxN = 1xN). For example:


Let's use code to test this concept:

>> m = LA.newMtx3(3,3,[1,2,3,4,5,6,7,8,9])
=> #
>> r = LA.newMtx3(1,3,[1,2,3]) # Row matrix
=> #
>> r1 = r*m # Row * Matrix = Row
=> #
>> puts r1
30 36 42
>> r2 = m.row2Mtx(0) + m.row2Mtx(1)*2 + m.row2Mtx(2)*3 # Row combination of Matrix
=> #
>> puts r2
30 36 42
=> nil
>> r1 == r2
=> true

Block Operations
If we divide Matrix into multiple blocks, then we can treat that block as an bigger element and do multiplication with block composition. For example:


Let's use code to test this concept:

>> A = LA.newMtx3(4,4,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16])
=> #
>> puts A
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
=> nil
>> B = LA.newMtx3(4,4,[1,0,2,0,0,1,0,2,3,0,4,0,0,3,0,4])
=> #
>> puts B
1 0 2 0
0 1 0 2
3 0 4 0
0 3 0 4
=> nil
>> C = A*B
=> #
>> puts C
10 14 14 20
26 30 38 44
42 46 62 68
58 62 86 92
=> nil
>> A11 = LA.newMtx3(2,2,[1,2,5,6])
=> #
>> A12 = LA.newMtx3(2,2,[3,4,7,8])
=> #
>> B11 = LA.newMtx3(2,2,[1,0,0,1])
=> #
>> B21 = LA.newMtx3(2,2,[3,0,0,3])
=> #
>> C11 = A11*B11 + A12*B21
=> #
>> puts C11
10 14
26 30
=> nil

Elimination Matrix
Actually, the elimination process can be presented with a matrix. For example:

Step1. Row1*-3 + Row2 to have Row2=[0,2,-2]

The row [-3, 1, 0] of the left matrix can be explained as operation on target matrix: Row1*-3 + Row2
E21 means this elimination matrix is to erase M[2,1] (M is target matrix) to be zero. For next step:

Step2. Row2*-2 + Row3 to have Row3=[0,0,5]

Finally, we get the elimination matrx:


Permutation
Consider we have a matrix like:

>> m = LA.newMtx3(2,2,[1,2,3,4])
=> #
>> puts m
1 2
3 4
=> nil

How do I switch column 0 with column 1 by matrix multiplication? Remember that we learn from different view of multiplication, the matrix multiplication can be column combination. So let's do it by multiple the matrix with a special matrix:

>> c = LA.newMtx3(2,2,[0,1,1,0])
=> #
>> puts c
0 1
1 0
=> nil
>> puts m*c # Here will switch column 0 with column 1 of matrix m
2 1
4 3

For the same principle, we can switch row by letting special matrix multiple our target multiple:

>> puts m
1 2
3 4
=> nil
>> r = LA.newMtx3(2,2,[0,1,1,0])
=> #
>> puts r*m # switch row 0 with row 1 of target matrix m
3 4
1 2