1.5-1.6 Solution Sets & Applications (Network Flow)

Theory: Solution Sets of Linear Systems & Applications

Homogeneous Linear Systems ( $A\mathbf{x} = \mathbf{0}$ )

A system of linear equations is said to be homogeneous if it can be written in the form:

A\mathbf{x} = \mathbf{0}

A homogeneous system is always consistent, since $\mathbf{x} = \mathbf{0}$ is always a solution (called the trivial solution).
The system $A\mathbf{x} = \mathbf{0}$ has a non-trivial solution (a non-zero vector $\mathbf{x} \ne \mathbf{0}$ ) if and only if the equation has at least one free variable (i.e. at least one non-pivot column).

Parametric Vector Form

When a system has free variables, the general solution can be written as an explicit linear combination of constant vectors with the free variables acting as parameters:

\mathbf{x} = t_1 \mathbf{v}_1 + t_2 \mathbf{v}_2 + \cdots + t_k \mathbf{v}_k

This is the parametric vector form of the solution set. The vectors $\mathbf{v}_1, \dots, \mathbf{v}_k$ span the solution space of $A\mathbf{x} = \mathbf{0}$ .

Non-homogeneous Systems ( $A\mathbf{x} = \mathbf{b}$ )

When $A\mathbf{x} = \mathbf{b}$ is consistent and has a particular solution $\mathbf{p}$ (meaning $A\mathbf{p} = \mathbf{b}$ ):

[!NOTE] Theorem 6: The solution set of $A\mathbf{x} = \mathbf{b}$ is the set of all vectors of the form:
$\mathbf{x} = \mathbf{p} + \mathbf{v}_h$
where $\mathbf{v}_h$ is any solution of the homogeneous equation $A\mathbf{v}_h = \mathbf{0}$ .

Geometrically, the solution set of $A\mathbf{x} = \mathbf{b}$ is a line (or plane/hyperplane) parallel to the solution set of $A\mathbf{x} = \mathbf{0}$ , translated away from the origin by the particular vector $\mathbf{p}$ .

Applications: Network Flow & Chemical Reactions (Lay §1.6)

Network Flow: At each junction (node) in a network, the total flow into the junction must equal the total flow out of the junction: $\sum \text{Flow In} = \sum \text{Flow Out}$ Also, total flow into the whole network equals total flow out of the network.
Balancing Chemical Equations: The number of atoms of each element on the left side (reactants) must equal the number on the right side (products), leading to a homogeneous linear system $A\mathbf{x} = \mathbf{0}$ solved for positive integer weights.

Solved Examples (Textbook Questions)

Exercise 1

(Adapted from Lay §1.5, Exercise 11)

Find the general solution of the homogeneous system $A\mathbf{x} = \mathbf{0}$ and express it in parametric vector form, where:

A = \begin{bmatrix} 1 & 3 & -3 & 7 \\ 0 & 1 & -4 & 5 \end{bmatrix}

Describe the solution set geometrically.

Show solution ↓

Solution

The augmented matrix is $[A \mid \mathbf{0}]$ :

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

Step 1: Reduce to RREF. Eliminate the entry above the pivot in column 2 ( $R_1 \leftarrow R_1 - 3R_2$ ):

[1, 3, -3, 7, 0] - 3[0, 1, -4, 5, 0] = [1, 0, 9, -8, 0]

The RREF is:

\left[\begin{array}{cccc|c} 1 & 0 & 9 & -8 & 0 \\ 0 & 1 & -4 & 5 & 0 \end{array}\right]

Step 2: Solve for basic variables.

Basic variables: $x_1, x_2$ .
Free variables: $x_3, x_4$ .

\begin{aligned} x_1 &= -9x_3 + 8x_4 \\ x_2 &= 4x_3 - 5x_4 \end{aligned}

Step 3: Write in parametric vector form.

\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} -9x_3 + 8x_4 \\ 4x_3 - 5x_4 \\ x_3 \\ x_4 \end{bmatrix} = x_3 \begin{bmatrix} -9 \\ 4 \\ 1 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} 8 \\ -5 \\ 0 \\ 1 \end{bmatrix}

Geometric description: The solution set is a 2-dimensional plane passing through the origin $\mathbf{0}$ in $\mathbb{R}^4$ , spanned by the vectors $\mathbf{u} = \begin{bmatrix} -9 \\ 4 \\ 1 \\ 0 \end{bmatrix}$ and $\mathbf{v} = \begin{bmatrix} 8 \\ -5 \\ 0 \\ 1 \end{bmatrix}$ .

Exercise 2

(Adapted from Lay §1.5, Exercise 15 & 16)

Write the general solution of $A\mathbf{x} = \mathbf{b}$ in parametric vector form, where:

A = \begin{bmatrix} 1 & 3 & 1 \\ -4 & -9 & 2 \\ 0 & 3 & -6 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 1 \\ -1 \\ -3 \end{bmatrix}

Compare the solution with the solution set of $A\mathbf{x} = \mathbf{0}$ .

Show solution ↓

Solution

Step 1: Set up the augmented matrix $[A \mid \mathbf{b}]$ and row reduce.

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

$R_2 \leftarrow R_2 + 4R_1$ : $[-4, -9, 2, -1] + 4[1, 3, 1, 1] = [0, 3, 6, 3]$
Scale $R_2 \leftarrow \frac{1}{3}R_2$ : $[0, 1, 2, 1]$
Scale $R_3 \leftarrow \frac{1}{3}R_3$ : $[0, 1, -2, -1]$

Matrix:

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

$R_3 \leftarrow R_3 - R_2$ : $[0, 1, -2, -1] - [0, 1, 2, 1] = [0, 0, -4, -2]$
Scale $R_3 \leftarrow -\frac{1}{4}R_3$ : $[0, 0, 1, 1/2]$

Backward phase to RREF:

$R_2 \leftarrow R_2 - 2R_3$ : $[0, 1, 2, 1] - 2[0, 0, 1, 1/2] = [0, 1, 0, 0]$
$R_1 \leftarrow R_1 - R_3$ : $[1, 3, 1, 1] - [0, 0, 1, 1/2] = [1, 3, 0, 1/2]$
$R_1 \leftarrow R_1 - 3R_2$ : $[1, 3, 0, 1/2] - 3[0, 1, 0, 0] = [1, 0, 0, 1/2]$

The RREF is:

\left[\begin{array}{ccc|c} 1 & 0 & 0 & 1/2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1/2 \end{array}\right]

Step 2: Conclusion. Every column has a pivot. There are no free variables. The system has a unique solution:

\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 1/2 \\ 0 \\ 1/2 \end{bmatrix}

In parametric vector form: $\mathbf{x} = \mathbf{p} + 0$ , where $\mathbf{p} = \begin{bmatrix} 1/2 \\ 0 \\ 1/2 \end{bmatrix}$ is the single point. The corresponding homogeneous system $A\mathbf{x} = \mathbf{0}$ has only the trivial solution $\mathbf{x} = \mathbf{0}$ .

Exercise 3

(Adapted from Lay §1.6, Exercise 1 - Network Flow)

The network shown below represents traffic flow (in vehicles per hour) through four intersections $A, B, C, D$ :

Intersection A: Inflow $300 + x_1$ ; Outflow $x_2 + 200$ .
Intersection B: Inflow $x_2 + 100$ ; Outflow $x_3 + x_4$ .
Intersection C: Inflow $x_3 + 400$ ; Outflow $x_5 + 300$ .
Intersection D: Inflow $x_4 + x_5$ ; Outflow $x_1 + 300$ .

Total inflow to the network is $300 + 100 + 400 = 800$ , and total outflow is $200 + 300 + 300 = 800$ .

Write a system of linear equations in the variables $x_1, x_2, x_3, x_4, x_5$ .
Find the general flow pattern by row reducing the augmented matrix.
If the road with flow $x_4$ is closed for repairs ( $x_4 = 0$ ), what are the remaining flows assuming all flows must be non-negative ( $x_i \ge 0$ )?

Show solution ↓

Solution

Step 1: Set up junction equations ( $\text{Flow In} = \text{Flow Out}$ ).

Node A: $300 + x_1 = x_2 + 200 \implies x_1 - x_2 = -100$
Node B: $x_2 + 100 = x_3 + x_4 \implies x_2 - x_3 - x_4 = -100$
Node C: $x_3 + 400 = x_5 + 300 \implies x_3 - x_5 = -100$
Node D: $x_4 + x_5 = x_1 + 300 \implies -x_1 + x_4 + x_5 = 300$

Step 2: Augmented matrix and row reduction.

\left[\begin{array}{ccccc|c} 1 & -1 & 0 & 0 & 0 & -100 \\ 0 & 1 & -1 & -1 & 0 & -100 \\ 0 & 0 & 1 & 0 & -1 & -100 \\ -1 & 0 & 0 & 1 & 1 & 300 \end{array}\right]

Add row 1 to row 4 ( $R_4 \leftarrow R_4 + R_1$ ):

[-1, 0, 0, 1, 1, 300] + [1, -1, 0, 0, 0, -100] = [0, -1, 0, 1, 1, 200]

Add row 2 to row 4 ( $R_4 \leftarrow R_4 + R_2$ ):

[0, -1, 0, 1, 1, 200] + [0, 1, -1, -1, 0, -100] = [0, 0, -1, 0, 1, 100]

Add row 3 to row 4 ( $R_4 \leftarrow R_4 + R_3$ ):

[0, 0, -1, 0, 1, 100] + [0, 0, 1, 0, -1, -100] = [0, 0, 0, 0, 0, 0]

Back-substitute to find basic variables ( $x_1, x_2, x_3$ ) in terms of free variables ( $x_4, x_5$ ):

From Row 3: $x_3 = x_5 - 100$
From Row 2: $x_2 = x_3 + x_4 - 100 = (x_5 - 100) + x_4 - 100 = x_4 + x_5 - 200$
From Row 1: $x_1 = x_2 - 100 = (x_4 + x_5 - 200) - 100 = x_4 + x_5 - 300$

General flow pattern:

\begin{cases} x_1 = x_4 + x_5 - 300 \\ x_2 = x_4 + x_5 - 200 \\ x_3 = x_5 - 100 \\ x_4, x_5 \text{ are free} \end{cases}

Step 3: Road $x_4$ is closed ( $x_4 = 0$ ). Setting $x_4 = 0$ :

x_1 = x_5 - 300, \quad x_2 = x_5 - 200, \quad x_3 = x_5 - 100, \quad x_4 = 0

Since all flows must be non-negative ( $x_i \ge 0$ ):

$x_1 \ge 0 \implies x_5 \ge 300$
$x_2 \ge 0 \implies x_5 \ge 200$
$x_3 \ge 0 \implies x_5 \ge 100$

The minimum flow required on road $x_5$ is $x_5 = 300$ . Under this minimum flow:

x_1 = 0, \quad x_2 = 100, \quad x_3 = 200, \quad x_4 = 0, \quad x_5 = 300.

1.5-1.6 Solution Sets & Applications (Network Flow)

Theory: Solution Sets of Linear Systems & Applications

Homogeneous Linear Systems (Ax=0A\mathbf{x} = \mathbf{0}Ax=0)

Parametric Vector Form

Non-homogeneous Systems (Ax=bA\mathbf{x} = \mathbf{b}Ax=b)

Applications: Network Flow & Chemical Reactions (Lay §1.6)

Solved Examples (Textbook Questions)

Homogeneous Linear Systems ( $A\mathbf{x} = \mathbf{0}$ )

Non-homogeneous Systems ( $A\mathbf{x} = \mathbf{b}$ )