This notebook requires latex_env nbextension for a correct visualization. Download and Installation's instructions available at http://jupyter-contrib-nbextensions.readthedocs.io/en/latest/nbextensions/latex_envs/README.html
Recall the following fact:
\begin{proposition} Proposition: Two matrices are row equivalent if and only if they represent the same linear map V \to W up to a choice of basis for W. \end{proposition}Any (possibly not square) finite matrix $B$ can be reduced in many ways by a finite sequence of Elementary Row-Operations $E_1, E_2, ...,E_m$, each one invertible, to a Reduced Row-Echelon Form (RREF) $$U := E_m \cdot\cdot\cdot E_2 \cdot E_1 \cdot B $$
characterized by three properties:
The entries which contain leading '1' so defined are called pivots.
In [5]:
import numpy as np
import sympy
M = np.array([[1,2,3,4,5],[1,2,3,4,6],[1,0,0,2,3]])
print(M)
print(sympy.Matrix(M).rref())
https://www.csun.edu/~panferov/math262/262_rref.pdf
https://www.math.purdue.edu/~shao92/documents/Algorithm%20REF.pdf
http://www.math.jhu.edu/~bernstein/math201/RREF.pdf
The reduced row echelon form is canonical, meaning it is uniquely determined for any matrix (this is not obvious, but for brevity we refer the reader to an external proof). https://people.eecs.berkeley.edu/~wkahan/MathH110/RREF1.pdf
https://www.di-mgt.com.au/matrixtransform.html, indeed the algorithm is gauss jordan elimination (check also this link https://gist.github.com/num3ric/1357315) We can deduce many useful facts about a matrix once it has been transformed to its canonical form. Let A denote a general matrix and let E
denote its RREF form.
Every matrix A
is row equivalent to a unique matrix E in row canonical (RREF) form. This means the form and elements of E are uniquely determined by A. So, if two matrices M and N both reduce to the same row canonical form E, then M∼N . The rank of a matrix A is equal to the number of pivots in E . This is one definition of rank. We write this as rank(A) or rk(A) . The rank of a matrix is equal to the dimension of both the row space and the column space. All invertible matrices reduce to the identity matrix I . If the n×n matrix A is invertible, then E is always the n×n identity matrix.
Recall the elementary row operations:
Elementary row operation corresponds to left multiplication of an appropriate matrix (elementary Matrix). Therefore. let $M$ be an $n \times m$ matrix,
The identity Matrix is, elementary, an elementary matrix. Elementary Matrices are invertible, and the inverse is an elementary matrix. And every product of elementary matrices is invertible.
Therefore we have the structure of a group, called the general linear group. (See Lie Groups)
https://www.youtube.com/watch?v=l69YjkuUym0
Is this the case?
Echelon (military) a formation in which units follow one another but are offset sufficiently to allow each unit a clear line of fire ahead. A step-like formation of troops. Any structure or group of structures arranged in a steplike form.
In other words, in echelon formation we arrange things so the row behind you won't shoot you.
In [1]:
import numpy as np
def rref(matrix):
# Check matrix dimension (useless in numpy)
numRows = len(matrix)
numCols = len(matrix[0])
nonzeroRow = 0
# Initialize to 0,0
i,j = 0,0
while True:
# Loop forever, and break when exceed indexes
# Why this choice?
if i >= numRows or j >= numCols:
break
# We are working over a field, any non 0 entry can be a pivot
# Search column wise for a non zero element
if matrix[i][j] == 0:
nonzeroRow = i
while nonzeroRow < numRows and matrix[nonzeroRow][j] == 0:
nonzeroRow += 1
# if none is found, check the next column
if nonzeroRow == numRows:
j += 1
# Go back at the beginning of the while loop
continue
# swap the two rows
temp = matrix[i]
matrix[i] = matrix[nonzeroRow]
matrix[nonzeroRow] = temp
# save the pivot value
pivot = matrix[i][j]
# Once we have found a pivot, we simply need to eliminate the remaining entries in the column.
#We know this won’t affect any previously inspected columns,
#because by the inductive hypothesis any entries which are to the left of our pivot are zero.???
# normalize, so the first is one is what is going on
matrix[i] = [x / pivot for x in matrix[i]]
for otherRow in range(0, numRows):
if otherRow == i:
continue
if matrix[otherRow][j] != 0:
matrix[otherRow] = [y - matrix[otherRow][j]*x
for (x,y) in zip(matrix[i], matrix[otherRow])]
i += 1; j+= 1
return matrix
# Note this works with python lists
# To Rewrite it in numpy for God's sake
bd1 = np.array([[-1,-1,-1,-1,0,0,0,0], [1,0,0,0,-1,-1,0,0],
[0,1,0,0,1,0,-1,-1], [0,0,1,0,0,1,1,0], [0,0,0,1,0,0,0,1]])
test = np.array([[-2,-2,4,-2],[-2,1,10,7],[-4,-4,-8,4],[4,-1,14,6]])
M = np.array([[1,2,3,4,5],[1,2,3,4,6],[1,0,0,2,3]])
toReduce = test.T.tolist()
print(np.array(rref(toReduce)))
print(test)
In [ ]: