\documentclass[12pt]{article}
\usepackage[pdftex]{graphicx}
\input{../macros.tex}
\begin{document}

\thispagestyle{plain}

\setcounter{session}{12}
\begin{center}
\textbf{Exercises on graphs, networks, and incidence matrices}
\end{center}

\begin{problem} 
(8.2 \#1.  {\em Introduction to Linear Algebra:} Strang) Write down
  the four by four incidence matrix $A$ for the square graph, shown
  below. (Hint: the first row has -1 in column 1 and +1 in column 2.)
  What vectors $(x_1, x_2, x_3, x_4)$ are in the nullspace of $\mb A$?
  How do you know that (1,0,0,0) is not in the row space of $\mb A$?

\begin{center}
\includegraphics[scale=.5]{fig1.png}
\end{center}
\end{problem}

\solution{
The incidence matrix $A$ is written as:
$$A =  
\left [  \begin{array}{rrrr} 
-1 & 1 & 0 & 0 \\
0 &  -1 & 1 & 0 \\
0 & 0 & 1 & -1 \\
-1 & 0 & 0 &  1\\  \end{array} \right ].$$
To find the vectors in the nullspace, we solve $A \vb x = \vb 0:$
%\begin{small}
$$ \left [ \begin{array}{rrrr} 
-1 & 1 & 0 & 0 \\
0 &  -1 & 1 & 0 \\
0 & 0 & 1 & -1 \\
-1 & 0 & 0 &  1\\  \end{array} \right ] \fourbyone {x_1} {x_2} {x_3} {x_4} = \fourbyone {x_2 - x_1} {x_3 - x_2} {x_3 - x_4} {x_4 - x_1} = \fourbyone 0 0 0 0,$$
%\end{small}
so  $x_1 = x_2 = x_3 = x_4$.  Therefore, the nullspace consists of vectors of the form $(a,a,a,a)$. 

Finally, (1,0,0,0) is not in the row space of $A$ because it is not orthogonal to the nullspace.
}

\begin{problem} 
(8.2 \#7.) Continuing with the network from problem one, suppose the
  conductance matrix is $$C = \left [  \begin{array}{rrrr} 1 & 0 & 0 &
      0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1
      \\ \end{array} \right ].$$ Multiply matrices to find $A^T C A.$
  For $\vb f = (1,0,-1,0)$, find a solution to $A^T C A \vb x = \vb f.$
  Write the potentials $\vb x$ and currents $\vb y = -C A \vb x$ on
  the square graph (see above) for this current source $\vb f$ going
  into node 1 and out from node 3.
\end{problem}

\solution{ From the previous question, we know that the incidence matrix is:
$$A =  
\left [ \begin{array}{rrrr} 
-1 & 1 & 0 & 0 \\
0 &  -1 & 1 & 0 \\
0 & 0 & 1 & -1 \\
-1 & 0 & 0 &  1\\  \end{array} \right ].$$ 
Multiply to obtain $A^T C A$:
\begin{small}
$$
\left [ \begin{array}{rrrr} 
-1 & 0 & 0 & -1 \\
1 & -1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
0 & 0 & -1 & 1 \\  \end{array} \right ] \left [ \begin{array}{rrrr} 
1 & 0 & 0 & 0 \\
0 & 2 & 0 & 0 \\
0 & 0 & 2 & 0 \\
0 & 0 & 0 & 1 \\  \end{array} \right ] \left [ \begin{array}{rrrr} 
-1 & 1 & 0 & 0 \\
0 &  -1 & 1 & 0 \\
0 & 0 & 1 & -1 \\
-1 & 0 & 0 &  1\\  \end{array} \right ] = 
\left [ \begin{array}{rrrr} 
2 & -1 & 0 & -1 \\
-1 & 3 & -2 & 0 \\
0 & -2 & 4 & -2 \\
-1 & 0 & -2 & 3 \\  \end{array} \right ].
$$
\end{small}

Solving the equation $A^T C A \vb x = \vb f$  by 
performing row reduction on the augmented matrix
$$\left[ \begin{array}{rrrr|r}
-1 & 0 & 0 & -1 & 1\\
1 & -1 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & -1\\
0 & 0 & -1 & 1 & 0\\  \end{array} \right ]
$$
and choosing $x_3 = 0$ to represent a grounded node gives: 
$$ \vb x = \fourbyone {x_1} {x_2} {x_3} {x_4} = \fourbyone {\textbf{3/4}} {\textbf{1/4}} {\textbf{0}} {\textbf{1/4}}.$$

We know $\vb y = -C A \vb x$, so
$$\vb y =  
\left [ \begin{array}{rrrr} 
1 & -1 & 0 & 0 \\
0 & 2 & -2 & 0 \\
0 & 0 & -2 & 2 \\
1 & 0 & 0 & -1 \\  \end{array} \right ] \fourbyone {3/4}{1/4}{0}{1/4} = \fourbyone {\textbf{1/2}}{\textbf{1/2}}{\textbf{1/2}}{\textbf{1/2}}.$$
We draw these values on the square graph:
\begin{center}
\includegraphics[scale=.65]{fig2.png}
\end{center}
}

\end{document}