Chapter4 Fundamentals of Linear Algebra

4.1 Introduction

Linear Algebra forms the backbone of various fields in computer science, including data science, machine learning, quantum computing, and cryptography. This module introduces foundational concepts through real-world examples, mathematical formulations, and Python implementations. Understanding these concepts is crucial for data representation, analysis, and computational techniques in advanced topics.

  • Introduce the system of linear equations using a simple linear equation in two space- eg., \[2x+y=11; 2x-y=10.\] Solve these equations in both algebraic and geometric methods (use Desmos or Cocalc). Explore the fact that the determinant of the coefficents of the system determine whether the lines are parallel or not.
  • Representation of the linear system as linear combination of column vectors with unknowns as coefficients- for example the above system can be represented as

\[ x\begin{pmatrix} 2\\ 2 \end{pmatrix}+y \begin{pmatrix} 1\\ -1 \end{pmatrix}= \begin{pmatrix} 11\\ 10\end{pmatrix} \]

  • Introduce the procedure for solving a system of linear equations using Gauss elimination method.
  • Present the linear system \[2x+y=11; 4x+2y=10.\] and try to solve it using Gauss elimination method. Demonstrate the fact that the solution leads to a mathematical falaci. This will leads to frame a systematic method to check consistency of the system. Now introduce the fundamental theorem of linear system.

4.1.1 1. Systems of Linear Equations

## Warning: package 'vembedr' was built under R version 4.2.3

A system of linear equations is a collection of one or more linear equations involving the same set of variables. For example:

\[ \begin{cases} a_1 x + b_1 y + c_1 z = d_1 \\ a_2 x + b_2 y + c_2 z = d_2 \\ a_3 x + b_3 y + c_3 z = d_3 \end{cases} \]

Simple Problem:

Solve the following system of equations:

\[ \begin{cases} x + y + z = 6 \\ 2x + 3y + 4z = 20 \\ 3x + 2y + z = 10 \end{cases} \]

4.2 Solution by Gauss Elimination

Gauss Elimination is a method for solving systems of linear equations. It involves three main operations: swapping rows, multiplying a row by a nonzero scalar, and adding or subtracting the multiples of rows to achieve an upper triangular matrix.

embed_url("https://youtu.be/QVKj3LADCnA?si=Ng7RznTZIjkqywSz")

Solve the system of equations using Gauss elimination:

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

Step-by-Step Solution:

Step 1: Write the augmented matrix \[ \left[\begin{array}{ccc|c} 2 & 3 & -1 & 5 \\ 4 & 1 & 2 & 6 \\ -2 & 3 & 2 & 4 \end{array}\right] \]

Step 2: Perform row operations to achieve an upper triangular form

Operation 1: \[ R2 \leftarrow R2 - 2R1 \]

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

Operation 2: \[ R3 \leftarrow R3 + R1 \]

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

Operation 3: \[ R3 \leftarrow R3 + \frac{6}{-5} R2 \]

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

Step 3: Perform back substitution

From the third row: \[ \frac{-19}{5}z = \frac{3}{5} \implies z = -\frac{3}{19} \]

Substitute \(z\) into the second row: \[ -5y + 4\left(-\frac{3}{19}\right) = -4 \implies y = -1 \]

Substitute \(y\) and \(z\) into the first row: \[ 2x + 3(-1) - (-\frac{3}{19}) = 5 \implies x = 3 \]

Solution:

\[ x = 3, \quad y = -1, \quad z = -\frac{3}{19} \]

4.2.1 Suggested examples

It is very important to transform the mathematical concepts as effective scientific tools for solving common problems in computer science. So select appropriate examples and its mathematical modelling along with practicing more problems. Through these problems both concept attainment and enhancement of problem solving skills are expected in both symbolic and computational aspects. So instructors are expected to demonstrate the programming and encourage students to solve tutorial/ assignment problems both in symbolic and computational approaches.

4.2.1.1 Real-Time Example 1: Network Traffic Analysis

You are analyzing network traffic across three routers. Each router records incoming and outgoing packets per minute. Given total packet counts and specific traffic patterns, determine the packet rates for each router.

Mathematical Formulation: Let \(x\), \(y\), and \(z\) be the packet rates for routers 1, 2, and 3, respectively. The system of equations is:

\[ \begin{cases} x + y + z = 200 \\ 1.5x + 2y + 3z = 450 \\ 2x + y + 2.5z = 400 \end{cases} \]

Solution: Using Gaussian elimination or matrix methods to solve the system.

Python Code:

import numpy as np

# Coefficients of the equations
A = np.array([[1, 1, 1],
              [1.5, 2, 3],
              [2, 1, 2.5]])

# Constants on the right-hand side
B = np.array([200, 450, 400])

# Solve the system of equations
solution = np.linalg.solve(A, B)
print("Packet rates for routers 1, 2, and 3:", solution)
## Packet rates for routers 1, 2, and 3: [71.42857143 42.85714286 85.71428571]

4.2.1.2 Real-Time Example 2: Distributed Computing Tasks

You have three servers processing tasks in a distributed computing environment. Each server handles a different number of tasks, and you want to balance the workload based on current processing capacities.

Mathematical Formulation:

Let \(x\), \(y\), and \(z\) be the number of tasks processed by servers 1, 2, and 3, respectively. The system of equations is:

\[ \begin{cases} x + 2y + 3z = 500 \\ 2x + y + z = 400 \\ x + y + 2z = 300 \end{cases} \]

Solution:

Using Gaussian elimination or matrix methods to solve the system.

Python Code:

import numpy as np

# Coefficients of the equations
A = np.array([[1, 2, 3],
              [2, 1, 1],
              [1, 1, 2]])

# Constants on the right-hand side
B = np.array([500, 400, 300])

# Solve the system of equations
solution = np.linalg.solve(A, B)
print("Number of tasks processed by servers 1, 2, and 3:", solution)

4.2.1.3 Real-Time Example 3: Sales Analysis of Three Products

You are analyzing the sales of three products (A, B, and C) across three stores. The total sales for each store and the price per unit for each product are known. Determine the quantity sold for each product in each store.

Mathematical Formulation:

Let \(x\), \(y\), and \(z\) be the quantities of products A, B, and C sold, respectively. The system of equations is:

\[ \begin{cases} 2x + 3y + z = 400 \\ x + 2y + 4z = 500 \\ 3x + y + 2z = 450 \end{cases} \]

Solution:

Using Gaussian elimination or matrix methods to solve the system.

Python Code:

# Coefficients of the equations
A = np.array([[2, 3, 1],
              [1, 2, 4],
              [3, 1, 2]])

# Constants on the right-hand side
B = np.array([400, 500, 450])

# Solve the system of equations
solution = np.linalg.solve(A, B)
print("Quantities of products A, B, and C sold:", solution)

4.2.1.4 Real-Time Example 4: Genetic Algorithm Optimization

In genetic algorithms, three parameters (mutation rate, crossover rate, and population size) influence algorithm performance. Given desired outcomes and constraints, determine optimal parameter values.

Mathematical Formulation:

Let \(x\), \(y\), and \(z\) be the parameters for mutation rate, crossover rate, and population size, respectively. The system of equations is:

\[ \begin{cases} x + 2y + z = 0.8 \\ 1.5x + y + 3z = 1.5 \\ 2x + y + 2z = 2.0 \end{cases} \]

Solution:

Using Gaussian elimination or matrix methods to solve the system (use pen and paper approach in the class room).

Python Code:

# Coefficients of the equations
A = np.array([[1, 2, 1],
              [1.5, 1, 3],
              [2, 1, 2]])

# Constants on the right-hand side
B = np.array([0.8, 1.5, 2.0])

# Solve the system of equations
solution = np.linalg.solve(A, B)
print("Optimal values for mutation rate, crossover rate, and population size:", solution)

4.2.1.5 Real-Time Example 5: Financial Portfolio Optimization

You have three investment options with different returns and risks. Given a target return and risk tolerance, determine the optimal investment allocation.

Mathematical Formulation:

Let \(x\), \(y\), and \(z\) be the investments in options A, B, and C, respectively. The system of equations is:

\[ \begin{cases} 1.2x + 0.8y + 1.5z = 15 \\ 0.5x + 1.5y + 1.2z = 10 \\ 1.8x + 1.2y + 0.5z = 20 \end{cases} \]

Solution:

Using Gaussian elimination or matrix methods to solve the system (use pen and paper approach in the class room).

Python Code:

# Coefficients of the equations
A = np.array([[1.2, 0.8, 1.5],
              [0.5, 1.5, 1.2],
              [1.8, 1.2, 0.5]])

# Constants on the right-hand side
B = np.array([15, 10, 20])

# Solve the system of equations
solution = np.linalg.solve(A, B)
print("Optimal investments in options A, B, and C:", solution)

4.2.2 Introduction to the Central Limit Theorem

The Central Limit Theorem (CLT) is a fundamental theorem in probability theory that explains why many distributions tend to be close to the normal distribution. It states that the distribution of the sum (or average) of a large number of independent, identically distributed random variables approaches a normal distribution, regardless of the original distribution of the variables.

4.2.2.1 Statement of the Central Limit Theorem

Let \(X_1, X_2, \ldots, X_n\) be a sequence of independent and identically distributed random variables with mean \(\mu\) and finite variance \(\sigma^2\). Then, as \(n\) approaches infinity, the distribution of the standardized sum of these random variables approaches a standard normal distribution. Mathematically, this can be expressed as:

\[ \frac{1}{\sqrt{n}} \left( \sum_{i=1}^n X_i - n\mu \right) \xrightarrow{d} \mathcal{N}(0, \sigma^2) \]

or equivalently,

\[ \frac{\sum_{i=1}^n X_i - n\mu}{\sigma \sqrt{n}} \xrightarrow{d} \mathcal{N}(0, 1) \]

where \(\xrightarrow{d}\) denotes convergence in distribution.

4.2.2.2 Practical Application in Computer Science

In computer science, the Central Limit Theorem is crucial for various applications, including:

  1. Algorithm Analysis: Estimating the average case performance of algorithms.
  2. Machine Learning: Understanding the distribution of sample means in training datasets.
  3. Quality Assurance: Monitoring and controlling the quality of software processes.
  4. Network Traffic: Modeling and predicting network load and data packet transmission times.

4.2.3 Example: Analyzing Network Traffic

Consider the scenario where we are analyzing the time taken for data packets to travel across a network. The travel times are influenced by various factors and may follow different distributions. However, by using the Central Limit Theorem, we can approximate the distribution of the average travel time for a large number of packets as a normal distribution.

4.2.4 Python Implementation with Interactive Demonstrations

We will simulate the travel times of data packets across a network using a uniform distribution and demonstrate the Central Limit Theorem by showing how the sample mean distribution approaches a normal distribution as the sample size increases.

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import ipywidgets as widgets
from IPython.display import display

# Function to update plot based on sample size
def update_plot(sample_size):
    np.random.seed(42)  # For reproducibility
    num_samples = 1000  # Number of samples

    # Simulate travel times (uniform distribution between 1 and 10 milliseconds)
    travel_times = np.random.uniform(1, 10, size=(num_samples, sample_size))

    # Calculate sample means
    sample_means = np.mean(travel_times, axis=1)

    # Plotting
    plt.figure(figsize=(12, 6))
    sns.histplot(sample_means, kde=True, color='blue')
    plt.title(f'Central Limit Theorem: Distribution of Sample Means (Sample Size = {sample_size})')
    plt.xlabel('Sample Mean')
    plt.ylabel('Frequency')
    plt.grid(True)
    plt.show()

# Create slider widget for sample size
sample_size_slider = widgets.IntSlider(value=10, min=10, max=500, step=10, description='Sample Size:')

# Display slider and plot
widgets.interactive(update_plot, sample_size=sample_size_slider)