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

# Reducing row echelon form #

\begin{definition}
two $n \times m$ matrices $A,B$ are row equivalent if there exists an invertible matrix $M$ with $B = MA$
\end{definition}

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:
1. The first nonzero element in any nonzero row is  “1” .
2. Each nonzero row's leading  “1”  comes in a column whose every other element is  “0” .
3. Each such leading  “1”  comes in a column after every preceeding row's leading zeros.

The entries which contain leading '1' so defined are called pivots. 


```python
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())
```

    [[1 2 3 4 5]
     [1 2 3 4 6]
     [1 0 0 2 3]]
    (Matrix([
    [1, 0,   0, 2, 0],
    [0, 1, 3/2, 1, 0],
    [0, 0,   0, 0, 1]]), (0, 1, 4))


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. 
    

## Elementary row operations: ##

Recall the elementary row operations: 

https://www.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations

 1. switch any two rows,
 2. multiply any row by a nonzero constant,
 3. add a nonzero (multiple of one) row to another row.

Elementary row operation corresponds to left multiplication of an appropriate matrix (elementary Matrix). Therefore. let $M$ be an $n \times m$ matrix,
1. $R_i \leftrightarrow R_j$ := $M \cdot I$ swapped 
2. $R_i \leftrightarrow cR_i$ := $M \cdot I$ with c on the ith entry 
3. $R_i + R_j \to R_k$ := $M \cdot I$ with 1 (or c) on the ith and jth entries

***
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. 



```python
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)
```

    [[-9.          0.          0.          0.        ]
     [ 0.45454545  1.          0.          0.        ]
     [ 0.54545455  0.          1.          0.        ]
     [ 0.27272727  0.          0.          1.        ]]
    [[-2 -2  4 -2]
     [-2  1 10  7]
     [-4 -4 -8  4]
     [ 4 -1 14  6]]



```python

```

742766312cd2f9e1aeb34c34ddcc01c8589e28c1
ipynb
Jupyter Notebook
RREF.ipynb
bramacchino/numberSense
996daa7a3543634d35a63d1ec77f3e5d28dcf9d3
MIT
RREF.ipynb
bramacchino/numberSense
996daa7a3543634d35a63d1ec77f3e5d28dcf9d3
MIT
RREF.ipynb
bramacchino/numberSense
996daa7a3543634d35a63d1ec77f3e5d28dcf9d3
MIT
Qwen/Qwen-72B
1. YES
2. YES