Menu
QuantML.orgQuantML.org
  • Linear Algebra
  • Null Space
  • Echelon Form
  • Solve
    \(A\vec{x}=0\)
  • RREF

    We discussed what a Null Space is, but how to find a Null space for an arbitrary large matrix, We can't do that by hands. So what are the steps (Algorithm) to find the Null space.

    Echelon Form

    To find Null Space first we convert our matrix (say
    \(A\)
    ) in echelon form using Elimination technique.
    For example Say our matrix is
    \(A=\begin{bmatrix} 1 & 2 & 2 & 2\\ 2 & 4 & 6 & 8\\ 3 & 6 & 8 & 10\\ \end{bmatrix}\)

    From now on we refer to
    \(i^{th}\)
    Row as
    \(r_i\)
    and
    \(j^{th}\)
    column as
    \(c_j\)

    box
    \(\fbox{}\)
    represent pivot element.
    Step 1: of elimination method, here we make all element
    \(0\)
    in
    \(c_1\)
    below the
    \(1^{st}\)
    element.
    \(r_2\leftarrow r_2-2r_1\)

    \(A=\begin{bmatrix} \fbox{1} & 2 & 2 & 2\\ 0 & 0 & 2 & 4\\ 3 & 6 & 8 & 10\\ \end{bmatrix}\)

    \(r_3\leftarrow r_3-3r_1\)

    \(A=\begin{bmatrix} \fbox{1} & 2 & 2 & 2\\ 0 & 0 & 2 & 4\\ 0 & 0 & 2 & 4\\ \end{bmatrix}\)

    Step 2: of elimination method, here we make all element
    \(0\)
    in
    \(c_2\)
    below the
    \(2^{nd}\)
    element.
    \(A=\begin{bmatrix} \fbox{1} & 2 & 2 & 2\\ 0 & 0 & 2 & 4\\ 0 & 0 & 2 & 4\\ \end{bmatrix}\)

    Here
    \(2^{nd}\)
    element itself is
    \(0\)
    , and all element below it also
    \(0\)
    , so move forward.
    Step 3: of elimination method, here we make all element
    \(0\)
    in
    \(c_3\)
    below the
    \(2^{nd}\)
    element.
    \(A=\begin{bmatrix} \fbox{1} & 2 & 2 & 2\\ 0 & 0 & 2 & 4\\ 0 & 0 & 2 & 4\\ \end{bmatrix}\)

    \(r_3\leftarrow r_3-r_2\)

    \(A=\begin{bmatrix} \fbox{1} & 2 & 2 & 2\\ 0 & 0 & \fbox{2} & 4\\ 0 & 0 & 0 & 0\\ \end{bmatrix}\)

    We end here because
    \(3^{rd}\)
    element of
    \(c_4\)
    is itself
    \(0\)

    So we got total
    \(2\)
    pivots, this is also the rank of this matrix.
    \(\text{Rank}(A)\)
    = # of pivots
    Our matrix has 4 columns,
    \(2\)
    of them are pivot columns and other we call free columns

    What are those pivot column and free columns?

    Free columns are dependent columns.
    And Pivot columns are independent columns.
    we can get those free columns by a linear combination of pivot columns.
    As in our example our pivot columns are
    \(c_1\)
    and
    \(c_3\)
    , and free columns are
    \(c_2\)
    and
    \(c_4\)

    \(A=\begin{bmatrix} 1 & 2 & 2 & 2\\ 2 & 4 & 6 & 8\\ 3 & 6 & 8 & 10\\ \end{bmatrix}\)

    We can get
    \(c_2\)
    as:
    \(c_2 = 2c_1\)

    We can get
    \(c_4\)
    as:
    \(c_4 = 2(c_3-c_1)\)