Gaussian Elimination 🎩📐🧠

Gaussian elimination is a foundational algorithm in linear algebra for solving systems of linear equations. The method systematically reduces a matrix to a simpler form—typically row-echelon or reduced row-echelon—allowing the solution to be extracted through back-substitution. 🔄🧮📊

---

Objective 🥅🎯📏

The goal is to transform a matrix using elementary row operations:

1. Row swap: Interchange two rows $( R_i \leftrightarrow R_j )$
2. Scalar multiplication: Multiply a row by a nonzero constant $( R_i \to k \cdot R_i )$
3. Row replacement: Replace a row with the sum or difference of itself and a multiple of another $( R_i \to R_i + k \cdot R_j )$

This yields a simpler matrix from which the solution set can be more easily determined. ✍️📐🔧

---

Worked Example 🪜📋🔢

Solve the system:

\begin{cases}
  x + y + z = 6 \\
  2y + 5z = -4 \\
  2x + 5y - z = 27
\end{cases}

Augmented matrix:

\left[\begin{array}{ccc|c}
1 & 1 & 1 & 6 \\
0 & 2 & 5 & -4 \\
2 & 5 & -1 & 27
\end{array}\right]

Step 1: Eliminate entry below first pivot $( R_3 \to R_3 - 2R_1 )$

\left[\begin{array}{ccc|c}
1 & 1 & 1 & 6 \\
0 & 2 & 5 & -4 \\
0 & 3 & -3 & 15
\end{array}\right]

Step 2: Normalize second pivot row $( R_2 \to \frac{1}{2} R_2 )$

Step 3: Eliminate below pivot in column 2 $( R_3 \to R_3 - 3R_2 )$

\left[\begin{array}{ccc|c}
1 & 1 & 1 & 6 \\
0 & 1 & 2.5 & -2 \\
0 & 0 & -10.5 & 21
\end{array}\right]

Step 4: Normalize final pivot row $( R_3 \to -\frac{1}{10.5} R_3 )$

---

Back Substitution 🔁🧠📉

From the final triangular system:

z = -2

y + 2.5z = -2 \Rightarrow y = 3

x + y + z = 6 \Rightarrow x = 5

Solution ✅🟢🧠

[ x = 5, \quad y = 3, \quad z = -2 ]

---

Row-Echelon vs. Reduced Row-Echelon 🔍🔢📏

• REF (Row-Echelon Form): Pivots are 1, all entries below each pivot are zero.
• RREF (Reduced Row-Echelon Form): Each pivot is the only nonzero entry in its column, allowing direct reading of the solution.

---

Summary 🧠📘📌

Gaussian elimination is a systematic technique for reducing linear systems to simpler forms using elementary row operations. Once in triangular form, back-substitution provides a clear path to the solution. The method is essential in both theoretical and computational linear algebra. 🧩✅📈

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Float_Text_IO; use Ada.Float_Text_IO;

procedure Gaussian_Elimination is

   -- Define a matrix type as a 2D array of floats
   type Matrix is array (
        Positive range <>, 
        Positive range <>) of Float;

   -- Define a vector type as a 1D array of floats
   type Vector is array (
        Positive range <>) of Float;
   
   procedure Print_Vector(V : Vector) is
        begin
        for I in V'Range loop
            Put("x" & Integer'Image(I) & " = ");
            Put(V(I), Fore => 1, Aft => 3, Exp => 0);
            New_Line;
            end loop;
        end Print_Vector;

   -- Procedure to perform forward elimination 
   ---- to convert matrix to upper triangular form
   procedure Eliminate(
        A : in out Matrix; 
        B : in out Vector) 
        is
        N : constant Positive := A'Length(1);
        begin
        for I in 1 .. N loop
            -- Find row with maximum absolute value in current column for pivoting
            declare
                Max_Row : Positive := I;
                Max_Val : Float := abs A(I, I);
                begin
                for K in I + 1 .. N loop
                    if abs A(K, I) > Max_Val then
                        Max_Val := abs A(K, I);
                        Max_Row := K;
                        end if;
                    end loop;
                -- Swap current row with row having maximum pivot
                if Max_Row /= I then
                    for J in 1 .. N loop
                        declare
                            Temp : Float := A(I, J);
                            begin
                            A(I, J) := A(Max_Row, J);
                            A(Max_Row, J) := Temp;
                            end;
                        end loop;
                    declare
                        Temp : Float := B(I);
                        begin
                        B(I) := B(Max_Row);
                        B(Max_Row) := Temp;
                        end;
                    end if;
                end;
            -- Eliminate entries below the pivot in the current column
            for K in I + 1 .. N loop
                declare
                    Factor : Float := A(K, I) / A(I, I);
                    begin
                    for J in I .. N loop
                        A(K, J) := A(K, J) - Factor * A(I, J);
                        end loop;
                    B(K) := B(K) - Factor * B(I);
                    end;
                end loop;
            end loop;
        end Eliminate;

   -- Function to perform back-substitution to find solution vector
   function Back_Substitute(
        A : Matrix; 
        B : Vector) 
        return Vector 
        is
        N : constant Positive := A'Length(1);
        X : Vector(1 .. N);
        begin
        for I in reverse 1 .. N loop
            declare
                Sum : Float := 0.0;
                begin
                -- Accumulate known terms from previously solved variables
                for J in I + 1 .. N loop
                    Sum := Sum + A(I, J) * X(J);
                    end loop;
                -- Solve for the current variable
                X(I) := (B(I) - Sum) / A(I, I);
                end;
            end loop;
        return X;
        end Back_Substitute;

   -- Example system
   A : Matrix(1 .. 2, 1 .. 2) :=
     (
      (2.0, 3.0), -- 2x + 3y = 4
      (4.0, -1.0) -- 4x + -y = -6
      );
   B : Vector(1 .. 2) := (4.0, -6.0);
   X : Vector(1 .. 2);

    begin
    -- Apply Gaussian elimination
    Eliminate(A, B);
    -- Solve the triangular system
    X := Back_Substitute(A, B);
    Put_Line("Solution:");
    Print_Vector(X);
    end Gaussian_Elimination;