PDF (letter size)
PDF (legal size)

Using Mason’s rule to solve \(Ax=b\)

Nasser M. Abbasi

January 5, 2019   Compiled on May 24, 2020 at 5:40am

This note shows how to solve \(Ax=b\) using Mason’s rule method. Mason rule is used to obtain the transfer function between two nodes in a signal graph, used in control systems, but can also be used to solve a set of linear equations. This shows an example of how to use this method to solve the following system\[ Ax=b \] Where\begin{equation} \begin{pmatrix} 2 & 1 & 3\\ 4 & 0 & -2\\ 1 & 2 & -1 \end{pmatrix}\begin{pmatrix} x_{1}\\ x_{2}\\ x_{3}\end{pmatrix} =\begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix} \tag{1} \end{equation} The solution to above, which can easily be found using Gaussian elimination is\begin{align*} x_{1} & =\frac{9}{17}\\ x_{2} & =\frac{-4}{17}\\ x_{3} & =\frac{1}{17} \end{align*}

The first step in Mason rule, is to decide on which are the variables that will be the nodes. Clearly here the variables are \(x_{1},x_{2},x_{3}\). So we write the three equations, with each one having one of those variables on the left side and everything to the right side. This gives the following three equations\begin{align} x_{1} & =\frac{1}{2}-\frac{1}{2}x_{2}-\frac{3}{2}x_{3}\nonumber \\ x_{3} & =-1+2x_{1}\tag{2}\\ x_{2} & =-\frac{1}{2}x_{1}+\frac{1}{2}x_{3}\nonumber \end{align}

The above three equations are a rewrite of the original three equations in (1). It does not matter which variable to move to the left from each equation, as long as we have one variable moved to the left each time. Now we draw the signal graph from (2). Each node is a variable. Arrows are drawn from the other variables (on the RHS) to the variable on the LHS. The weight on the arrow is the coefficient next to each other variable. We use the number \(1\) as a node since it stands on its own. The result is the following diagram

Figure 1:Mason graph

We now need to decide which is the input and which is the output. If we want to solve for \(x_{3}\) first, then we make \(x_{3}\) the output and always make the numerical value \(1\) as input, since it is known. Hence we are looking for the transfer function \(\frac{Y}{U}=\frac{x_{3}}{1}=x_{3}\). The first step in Mason method is to find all forward paths from \(U\) to \(Y\). There are two in this case, they are\begin{align*} F_{1} & =\left ( \frac{1}{2}\right ) \left ( 2\right ) =1\\ F_{2} & =-1 \end{align*}

Next we find all closed loops, there are three\begin{align*} L_{1} & =\left ( 2\right ) \left ( \frac{1}{2}\right ) \left ( -\frac{1}{2}\right ) =-\frac{1}{2}\\ L_{2} & =\left ( -\frac{1}{2}\right ) \left ( -\frac{1}{2}\right ) =\frac{1}{4}\\ L_{3} & =\left ( 2\right ) \left ( -\frac{3}{2}\right ) =-3 \end{align*}

Next we find \(\Delta _{i}\) associated with each \(F_{i}\). These are found by removing \(F_{i}\) path from the graph and recalculated the Mason \(\Delta \) for what is left. In this case we see that \(\Delta _{1}=1\) and \(\Delta _{2}=1-\frac{1}{4}=\frac{3}{4}\). Now we are ready to find \(\frac{Y}{U}=x_{3}\)\[ x_{3}=\frac{{\sum \limits _{i}}F_{i}\Delta _{i}}{1-{\sum \limits _{i}}L_{i}}=\frac{F_{1}\Delta _{1}+F_{2}\Delta _{2}}{1-\left ( -\frac{1}{2}+\frac{1}{4}-3\right ) }=\frac{1-1\left ( \frac{3}{4}\right ) }{1-\left ( -\frac{1}{2}+\frac{1}{4}-3\right ) }=\frac{1}{17}\] Now that we found one variable, we do the same for the next variable. Let us pick \(x_{2}\) as the output \(Y\) now, so we are looking for \(\frac{Y}{U}=\frac{x_{2}}{1}=x_{2}\). In this case, there are four forward paths from \(1\) to \(x_{2}\) \begin{align*} F_{1} & =\left ( \frac{1}{2}\right ) \left ( -\frac{1}{2}\right ) =-\frac{1}{4}\\ F_{2} & =\left ( -1\right ) \left ( \frac{1}{2}\right ) =-\frac{1}{2}\\ F_{3} & =\left ( \frac{1}{2}\right ) \left ( 2\right ) \left ( \frac{1}{2}\right ) =\frac{1}{2}\\ F_{4} & =\left ( -1\right ) \left ( -\frac{3}{2}\right ) \left ( -\frac{1}{2}\right ) =-\frac{3}{4} \end{align*}

The loops remain the same as before, since the loops do not change as the graph remains the same. We now just need to recalculate the \(\Delta _{i}\) associated with each \(F_{i}\). From the graph we see that \(\Delta _{1}=1,\Delta _{2}=1,\Delta _{3}=1\) and \(\Delta _{4}=1\) Hence\[ x_{2}=\frac{{\sum \limits _{i}}F_{i}\Delta _{i}}{1-{\sum \limits _{i}}L_{i}}=\frac{F_{1}\Delta _{1}+F_{2}\Delta _{2}+F_{3}\Delta _{3}+F_{4}\Delta _{4}}{1-\left ( -\frac{1}{2}+\frac{1}{4}-3\right ) }=\frac{-\frac{1}{4}-\frac{1}{2}+\frac{1}{2}-\frac{3}{4}}{1-\left ( -\frac{1}{2}+\frac{1}{4}-3\right ) }=-\frac{4}{17}\] Now we will find the final unknown, which is \(x_{1}\). Now \(x_{1}\) is the output. In this case, there are three forward paths from \(1\) to \(x_{2}\) \begin{align*} F_{1} & =\left ( \frac{1}{2}\right ) \\ F_{2} & =\left ( -1\right ) \left ( \frac{1}{2}\right ) \left ( -\frac{1}{2}\right ) =\frac{1}{4}\\ F_{3} & =\left ( -1\right ) \left ( -\frac{3}{2}\right ) =\frac{3}{2} \end{align*}

Now we find the \(\Delta _{i}\) associated with each \(F_{i}\). From the graph we see that \(\Delta _{1}=1,\Delta _{2}=1,\Delta _{3}=1\) Hence\[ x_{1}=\frac{{\sum \limits _{i}}F_{i}\Delta _{i}}{1-{\sum \limits _{i}}L_{i}}=\frac{F_{1}\Delta _{1}+F_{2}\Delta _{2}+F_{3}\Delta _{3}}{1-\left ( -\frac{1}{2}+\frac{1}{4}-3\right ) }=\frac{\frac{1}{2}+\frac{1}{4}+\frac{3}{2}}{1-\left ( -\frac{1}{2}+\frac{1}{4}-3\right ) }=\frac{9}{17}\] Therefore the three variables are \begin{align*} x_{1} & =\frac{9}{17}\\ x_{2} & =\frac{-4}{17}\\ x_{3} & =\frac{1}{17} \end{align*}