IFN Lab: Stochastic to Ideal Flow Matrix

Brief Description

A nonnegative matrix $ \mathbf{S} $ is called a stochastic matrix if all its row sums are one. From an irreducible stochastic matrix $ \mathbf{S} $, we can transform it into an ideal flow matrix $ \mathbf{F} $ whose total flow is $ \kappa $. An ideal flow matrix is a nonnegative matrix that is premagic and irreducible. Premagic matrix is a square matrix where the sum of rows is equal to the transpose of the sum of columns.

Let $ \mathbf{C} = [c_{ij}] $ be the capacity matrix, $ \kappa $ be the parameter, and $ \mathbf{j} $ be the column vector of ones. Then, the stochastic matrix $ \mathbf{S} $ is given by proportional formula: $$ \textbf{S}=\textbf{C} \: ./ \left ( \textbf{C}\textbf{j}\textbf{j}^{T} \right ) $$ Symbol ./ represent elementwise division where division by zero remains zero by definition. Let $ \textbf{I} $ be the identity matrix, then the node vector $ \mathbf{\pi} $ is computed with parameter total flow $ \kappa $ as $$ \mathbf{\pi} =\begin{bmatrix} \mathbf{S}^{T}-\mathbf{I} \\ \mathbf{j}^{T} \end{bmatrix} \setminus \begin{bmatrix} \mathbf{0} \\ \kappa \end{bmatrix} $$ The notation $ \mathbf{x} = \mathbf{K} \setminus \mathbf{b} $ means $ \mathbf{x} = \mathbf{K}^{+} \mathbf{b} $ where $ \mathbf{K}^{+} = (\mathbf{K}^{T}\mathbf{K})^{-1} \mathbf{K}^{T} $ is the Generalized Left Inverse of the Moore Penrose Inverse.The notation $ \mathbf{x} = \mathbf{K} \setminus \mathbf{b} $ means $ \mathbf{x} = \mathbf{K}^{+} \mathbf{b} $ where $ \mathbf{K}^{+} = (\mathbf{K}^{T}\mathbf{K})^{-1} \mathbf{K}^{T} $ is the Generalized Left Inverse of the Moore Penrose Inverse. From the node vector $ \mathbf{\pi} $ and stochastic matrix $ \mathbf{S} $ we can compute the flow matrix . $$ \mathbf{F} = \left (\mathbf{\pi} \cdot \mathbf{j}^{T} \right ) \circ \mathbf{S} $$

Learning Objectives

to compute Ideal Flow matrix and network based on stochastic matrix up to a scale.
to comprehend the pattern of irreducible or irreducible matrix.
to comprehend the pattern of premagic matrix
to compare the ideal flow matrix from reducible or irreducible stochastic matrix
to demonstrate the premagic pattern of the ideal flow matrix
to compare various total flow of the ideal flow matrix

Prerequisite

Read: Graph Theory and Linear Algebra

Instruction

Use the lab tool below to convert a Stochastic matrix into an Ideal Flow matrix.

Generate random stochastic matrix by clicking or to generate random Irreducible Stochastic matrix. You can also modify the matrix manually. End each row by a semicolon. Separate each data in one row by comma or a space.
Set total flow and click to convert the stochastic matrix into an ideal flow matrix. Your network must be strongly connected.
Alternatively, set total flow and click to forcely convert the stochastic matrix into an ideal flow matrix. Your network can be weakly connected.

Experiment and Discussion

Try the effect of parameter $ \kappa $.

Set various value for $ \kappa $ and check the total flow on the matrix by hovering on the bottom right cell. What is the meaning of parameter $ \kappa $?
Change the value of $ \kappa $ such that the result ideal flow are all integers. Use fraction form and find the least common multiple of the denominators?

Investigate pattern of stochastic matrix

What is the sum of each row in the stochastic matrix? Hover your mouse on the sum of each row
Create random stochastic matrix which is reducible. What happens to the pattern of the ideal flow?
Create random stochastic matrix which is irreducible. What happens to the pattern of the ideal flow?
Create random stochastic matrix which is premagic. What happens to the pattern of the ideal flow?

Challenge yourself

If your stochastic matrix contains a source node, what would happen to the ideal flow matrix?
If your stochastic matrix contains a sink node, what would happen to the ideal flow matrix?
If your stochastic matrix contains a source component, what would happen to the ideal flow matrix?
If your stochastic matrix contains a sink component, what would happen to the ideal flow matrix?

Lab Tool: Stochastic to Ideal Flow

Generate Random Irreducible Stochastic Matrix

size

Stochastic matrix
Is Fraction:
0, 0, 0.9, 0.1; 0, 0, 0.2, 0.8; 0.7, 0.3, 0, 0; 0.1, 0.9, 0, 0;

Pattern of Stochastic Matrix

$ \kappa $:

Forced to convert Stocastic to Ideal Flow Matrix

Flow matrix
Is Fraction:

Pattern of Flow Matrix

IFN Lab: Stochastic to Ideal Flow Matrix

Index