Description

Properties of State Transition Matrices

General Properties

1. Each arrow corresponds to the proportion of a node that is being transferred to another node (each entry will be $\leq 1$).
2. The only arrows that are present are the arrows that are drawn. A nonexistent arrow implies that the flow between the nodes is $0$. Do not add arrows to make the total flow leaving the node sum to one.
3. A row corresponds to the inflow to a node.

4. A column corresponds to the outflow of the node.

5. If any of the rows are linearly dependent, the transition matrix is not invertible!

6. However, when you apply a dependent transition matrix to a vector, the two corresponding entries to the dependent rows in the vector with be related (i.e. if $row_1 = 2 \cdot row_2$, then the resulting vector will have $entry_1 = 2 \cdot entry_2$).

Column Properties

1. If the entries in each columns sum to one, this means that whatever is being transferred is conserved. This means nothing is lost and gained as the matrix is applied!

2. If the entries in each columns sum to less than one, this means that the system is gradually losing whatever is being transferred.

3. If the entries in each columns sum to more than one, this means that the system is gradually gaining whatever is being transferred.

Procedure

Label each column with a node. Label each row with a node. We can view the columns as where the arrow is FROM and the rows as where the arrow is going TO. For example, let's consider a system with two nodes, A and B.

Transition Matrix

The value corresponding to the entry at (A, A) is the arrow that goes from node A to node A. The entry at (B, A) is the arrow that goes from node B and goes to node A.

Example

Graph	Incidence Matrix
	$$\begin{bmatrix}

e{AA} & e{BA} &e{CA} \ e{AB} &e{BB} & e{CB} \ e{AC} &e{BC} & e_{CC} \ \end{bmatrix}

We will fill out this transition matrix to correspond with the picture. The first entry of the subscript represents where the arrow is coming from. The second entry of the subscript represents where the arrow is going towards. Entry $$e_{BA}$$ corresponds to the arrow that is coming from B to A. ##### Row Approach We can fill the transition matrix out row by row. Each row represents the total inflow into a node. Let's focus on the inflow into node A which is the first row. The first entry, $$e_{AA}$$, corresponds to the arrow that goes from A to A. However, there is no arrow there. This means we assume that there is no flow from node A to A. So $$e_{AA} = 0$$. How about entry $$e_{BA}$$? The arrow that goes _from_ B _to_ A has a value of 0.3. This means the entry at $$e_{BA} = 0.3$$. By the same logic, $$e_{CA} = 0.3$$. ##### Column Approach We can also the fill the transition matrix out column by column. Each column represents the total outflow from a node. Let's focus on node B instead this time. B gives 0.3 to A, .3 for itself, and 0.4 to C. This would correspond to $$e_{BA} = 0.3, e_{BB} = 0.3, e_{BC} = 0.4$$. Apply either approach to fully solve the transition matrix. The resulting transition matrix is $$\begin{bmatrix} 0 & 0.3 &0.3 \\ 0.5 &0.3 &0.7 \\ 0.5&0.4 & 0 \\ \end{bmatrix}

Because the sum of each column is equal to one, the system is conservative.

Notation for Incidence Matrices

In edge-node incidence matrices, columns represent nodes while edges represent rows. Flow into a node in represented by $-1$ while flows out of a node are represented by $+1$ in the respective entry in the incidence matrix. This convention is very important when it comes to circuits so be sure use this convention!

Example

Graph	Incidence Matrix
	$$\begin{bmatrix}

1 & -1 & 0 & 0\ 0 & 1 & -1 & 0\ -1 &0 & 1 & 0\ 1 & 0 & 0 & -1 \end{bmatrix}

#### Row approach The matrix above was created for the directed graph. Because it has four nodes ($$a, b, c, d$$), it has 4 columns. The four edges corresponds to the four rows. Let's derive the first row of the matrix. For edge one, it is leaving node $$a$$ and entering node $$b$$. Therefore, the first entry (corresponding to node $$a$$) in row one will be $$1$$ and the second entry (corresponding to node $$b$$) in row one will be $$-1$$. For edge 2, the arrow is leaving node $$b$$ and entering node $$c$$. Therefore, the second entry is $$1$$ and the third entry is $$-1$$. The rest of the rows in this matrix is constructed in the same manner. #### Column approach We can also construct the matrix by focusing on the flows in and out of nodes. The first column corresponds to node $$a$$ while the first entry corresponds to edge 1, second entry edge 2, and so on. To construct each column, we look at which edges are entering and leaving the node. For every entry that corresponds with an edge into the node, we will place a $$-1$$. For every entry that corresponds with an edge out of the node, we will place $$1$$. For column one (which corresponds with node $$a$$), edge one and four are flowing out, so we place a $$1$$ in the first and fourth entry. Edge three is flowing in, so we place a $$-1$$ in the third entry. The rest of the rows can be constructed this way until all the columns are filled. #### Sanity Checks * All rows should add up to zero! This is because for each edge, it can only leave one node and enter another (it can flow back to itself though). * Make sure that the number of nodes equals the number of columns. * Make sure that the number of edges equals the number of rows. #### Preview of Future Material Soon we'll be applying incidence matrices to circuits to show two fundamental laws: Kirchoff's Voltage Law and Kirchoff's Current Law. Multiplying the incidence matrix by a vector containing all the node potentials will give you potential differences across each edge. By taking the transpose of the incidence matrix and multiplying it by a vector containing the flows will give you all the flows in and out of a node. Let's look at the example from earlier: Nodes a, b, c, and d will represent voltages when we dive into circuits later. (Don't worry about knowing what voltage is yet--this is just a preview!) Graph | Incidence Matrix :----------------:|:-------------------:  | $$\begin{bmatrix} 1 & -1 & 0 & 0\\ 0 & 1 & -1 & 0\\ -1 &0 & 1 & 0\\ 1 & 0 & 0 & -1 \end{bmatrix}

Multiplying the incidence matrix by a vector containing all the nodes: $\begin{bmatrix} 1 & -1 & 0 & 0\\ 0 & 1 & -1 & 0\\ -1 &0 & 1 & 0\\ 1 & 0 & 0 & -1 \end{bmatrix} \begin{bmatrix}a\\b\\c\\d\\ \end{bmatrix} = \begin{bmatrix}a - b\\b - c\\c - a\\a - d\\ \end{bmatrix}$ As you see, we will get the potential difference across each edge (Entry 1 corresponds to flow 1 etc).

Let's do the same thing again but with the transpose of the matrix times a vector containing the flows.

Let's denote each edge as i. In this example, there are four flows, $i_1, i_2, i_3$, and $i_4$. $\begin{bmatrix} 1 & 0 & -1 & 1\\ -1 & 1 & 0 & 0\\ 0 &-1 & 1 & 0\\ 0 & 0 & 0 & -1 \end{bmatrix} \begin{bmatrix}i_1\\i_2\\i_3\\i_4\\ \end{bmatrix} = \begin{bmatrix}i_1 - i_3 + i_4\\i_2 - i_1\\i_3 - i_2\\-i_4\\ \end{bmatrix}$ As you see, each entry in the resulting vector shows the flows in and out of each node. We will go more into depth about what exactly this means in the future lectures about circuits!