Solving System of Linear Equations Using Row Operations/Gaussian Elimination

1. Elementary Row Operations (also known as Gaussian Elimination) can be used to Find Solutions for Both Homogeneous and Non-Homogeneous System of Linear Equations.
2. Given following System of Linear Equations having \(M\) Equations and \(N\) Variables
   
   \(a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = k_1\)
   \(a_{21}x_1 + a_{22}x_2 + ... + a_{1n}x_n = k_2\)
   \(\vdots \)
   \(a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n = k_{m}\)
   
   The Co-efficients, Variables, and the Constants of the above Equations can be represented by the following Matrices
   
   \(A=\begin{bmatrix} a_{11} & a_{12} & ... & a_{1n}\\ a_{21} & a_{22} & ... & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{m1} & a_{m2} & ... & a_{mn}\end{bmatrix} \hspace{.5cm} X=\begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \hspace{.5cm} K=\begin{bmatrix} k_1 \\ k_2 \\ \vdots \\ k_m \end{bmatrix}\)
3. Following gives the steps for solving the System of Linear Equations as given above using Elementary Row Operations/Gaussian Elimination
   1. Represent the System of Linear Equations using following Matrix Equation
      
      \(AX=K \Rightarrow \begin{bmatrix} a_{11} & a_{12} & ... & a_{1n}\\ a_{21} & a_{22} & ... & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{m1} & a_{m2} & ... & a_{mn}\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}=\begin{bmatrix} k_1 \\ k_2 \\ \vdots \\ k_m \end{bmatrix}\)   ...(1)
   2. Perform Elementary Row Operations as given in the Algorithm on the Co-efficient Matrix \(A\) on the Left Hand Side of the Matrix Equation. Simultaneously, perform the same Elementary Row Operations on the Constant Matrix/Vector \(K\) on the Right Hand Side of the Matrix Equation.
      
      Following can be the outcomes of the Elementary Row Operations on Co-efficient Matrix \(A\) and Constant Matrix/Vector \(K\)
      1. If After Row Operations Any One of the Rows of Co-efficient Matrix \(A\) becomes 0 but the Corresponding Row of Constant Matrix/Vector \(K\) is Not Zero, then the System of Linear Equations has No Solutions.
      2. If After Row Operations the Co-efficient Matrix \(A\) gets converted to a Matrix having only Mutually Orthogonal Identity Vectors (i.e. Vectors having 1 as One of the Components and 0 as Other Components), then the System of Linear Equations has a Unique Solution given by the Elements of the Constant Matrix/Vector \(K\), which give the Values of Variables specified by Corresponding Elements in Variable Matrix/Vector \(X\).
         For Homogeneous System of Linear Equations, this solution is the Trivial Solution where Values of All Variables \(x_1=x_2=...=x_n=0\).
      3. If After Row Operations Co-efficient Matrix \(A\) has Vectors Other Than Mutually Orthogonal Identity Vectors, then the System of Linear Equations has Infinitely Many Solutions. The Solution for such System of Linear Equations are given in terms of Relation between the Variables of the Variable Matrix/Vector \(X\) as determined by the System of Linear Equations given by the updated Co-efficient Matrix \(A\) and the Variable Matrix \(X\).
         For Homogeneous System of Linear Equations, these solutions are also called Non Trivial Solutions.