Gaussian Elimination

Theory : 

Gaussian Elimination is a method used in linear algebra to solve systems of linear equations. It transforms a system’s augmented matrix into a simpler form called row echelon form (and sometimes further to reduced row echelon form) using a sequence of row operations:

1. Swapping two rows

2. Multiplying a row by a nonzero constant

3. Adding or subtracting a multiple of one row to another

The goal is to create zeros below the leading coefficients (pivots) in each row, forming a triangular matrix. Once in this form, the solution can be found through back-substitution.

It’s a systematic and efficient method for:

• Solving linear systems

• Finding the rank of a matrix

• Determining the inverse of a matrix (if it exists)

Application problem :

A blockchain network consists of three validating nodes, N1, N2, and N3, responsible for verifying and storing transactions. Due to increasing transaction volume, the network administrators must ensure an optimal distribution of computational resources among these nodes. →Let 2, and x, represent the number of transactions (in thousands) processed by N1, N2, and N3, respectively. The system must satisfy the following conditions: The total number of transactions processed across all nodes is 900,000. N1 handles 50% more transactions than N2. →The sum of transactions processed by N2 and N3 is 1.5 times the transactions handled by N1. To ensure secure and efficient blockchain operations, formulate a system of linear equations and use Gaussian Elimination to determine the exact transaction distribution across the network to optimize workload distribution and prevent traffic on blockchain network.

Reflection Questions : 

1. What would happen if the system had no unique solution? How could that affect transaction processing?

If a system (e.g. a set of equations used in transaction processing) has no unique solution, it means the system is either inconsistent (no solution at all) or underdetermined (infinitely many solutions).

2. What happens if one of the equations is dependent on the others? Would the system still be solvable?

If one equation is dependent (i.e., a linear combination of others), then the system becomes underdetermined.

It would still be solvable, but the solution wouldn't be unique — there would be infinitely many valid solutions.

In the blockchain case, multiple transaction distributions could satisfy the constraints, but without additional conditions, the best distribution (e.g., most efficient or secure) would be unclear.

Extra constraints or optimization techniques (like minimizing load variance) might be needed to pick the most appropriate solution.

3. How could we detect and handle an inconsistent or redundant system of equations?

Detection

To detect inconsistencies or redundancies in a system of equations, we can use matrix methods such as Gaussian Elimination or convert the system to Row Reduced Echelon Form (RREF).

• Redundant (Dependent) Equations:
  A redundant equation is one that can be written as a linear combination of other equations. In matrix form, these show up as rows of all zeros in RREF, indicating that the equation does not provide new information.

• Inconsistent Equations:
  An inconsistent system has conflicting equations with no solution. This is detected when RREF results in a row like:

[0  0  0 | c]  where c ≠ 0

This indicates a contradiction (e.g., 0 = 5), meaning the system has no solution.

Handling

• Handling Redundancy:

  • Remove redundant equations to simplify the system.

  • Improve computational efficiency by reducing the number of equations.

  • Use symbolic math tools (like SymPy in Python or MATLAB) to automatically identify and eliminate redundant equations.

• Handling Inconsistency:

  • Abort any dependent processing (e.g., stop a transaction or computation).

  • Log the issue and notify the user or system administrator.

  • Ensure that conflicting rules or constraints are reviewed and corrected.

  • In systems like databases or financial processing, roll back affected transactions to maintain integrity.

What does the code do during the forward elimination and back substitution steps?

Forward Elimination

During the forward elimination step, the code transforms the system of linear equations (represented as an augmented matrix) into an upper triangular form. The goal is to eliminate the variables below the main diagonal, making it easier to solve the system step-by-step.

Key operations:

• Select a pivot element (typically the first non-zero entry in a row).

• Use the pivot to eliminate the corresponding variable from all rows below.

• Subtract a suitable multiple of the pivot row from the lower rows to make the elements below the pivot zero.

• Repeat the process for each column from left to right.

Back Substitution

After forward elimination, the matrix is in upper triangular form. The code then performs back substitution to find the solution of the system, starting from the last equation and moving upward.

Key operations:

• Start from the last row, which contains only one variable.

• Solve for that variable.

• Substitute the known variable into the equations above it to find the remaining unknowns.

• Continue moving upward until all variables are solved.