In the incidence matrices, the rows indicate the edges, and the columns are the nodes. We put \(-1\) for the node that the edge leaves and \(+1\) for the node that the edges arrives at. Arrows are used to indicate direction.\[ A_{1}=\begin{pmatrix} -1 & +1 & 0 & 0\\ 0 & -1 & 1 & 0\\ 0 & 0 & -1 & +1\\ 1 & 0 & 0 & -1 \end{pmatrix} ,A_{2}=\begin{pmatrix} -1 & +1 & 0 & 0 & 0\\ 0 & -1 & +1 & 0 & 0\\ 0 & 0 & -1 & +1 & 0\\ 0 & 0 & 0 & -1 & +1\\ 0 & 0 & -1 & 0 & +1\\ -1 & 0 & +1 & 0 & 0 \end{pmatrix} \] We first note that matrix \(A_{1}\) rank \(r=3,m=4,n=4\).
In \(A_{1}x=b\), the vectors \(b\) have to be in the column space of \(A_{1}\). These are vectors in \(R^{m}=R^{4},\) that span space of dimension \(r=3\). Since there is a cycle (starting from node \(1\) we end up at node \(1\) again by following the edges), this means that all the potentials at each node must be the same. But if the potential at each node is the same, then there can be no flow of current. Since flow of current represent the edge, it means each edge will have zero value. So \(b\) must be all vectors/edges that add up to \(\left [ 0,0,0,0\right ] \) vector. For the case of \(A_{1}^{T}\), we obtain the matrix\[ A_{1}^{T}=\begin{pmatrix} -1 & 0 & 0 & 1\\ +1 & -1 & 0 & 0\\ 0 & +1 & -1 & 0\\ 0 & 0 & +1 & -1 \end{pmatrix} \] \(N\left ( A_{1}^{T}\right ) \) in the space of \(R^{m}=R^{4}\) with vectors that span dimension space \(m-r=4-3=1\). So a line. So one basis vector is all what is needed.
And now we ask about the nodes of this graph. What values can they have? This is the graph associated with this matrix
We now ask, what values should the nodes have in order for the edges to have zero flow in them? It is clear the nodes must all be equal \(\left [ 1,1,1,1\right ] \) since if the potential is same at each node, then there will be no flow (i.e. zero potential difference) on the edges. Therefore \[ \fbox{$N\left ( A^T\right ) =\left [ 1,1,1,1\right ] $}\] We also know from fundamental theory of linear algebra, that \(R\left ( A\right ) \) is orthogonal to \(N\left ( A^{T}\right ) .\)
The matrix \(A_{2}\) has rank \(r=4,m=6,n=5.\)The number of independent rows (edges) is \(n-1\) or \(5-1=4\) which is its rank. These can be read from the graph directly. Any \(4\) edges, as long as they do not complete a cycle, will qualify. Hence the edges that meet this condition are\begin{align*} & 6,5,4,2\\ & 6,5,4,1\\ & 6,5,3,2\\ & 6,5,3,1\\ & 6,4,3,2\\ & 6,4,3,1\\ & 5,4,2,1\\ & 5,3,2,1\\ & 4,3,2,1 \end{align*}
Notice that we could not have selected for example \(6,5,4,3\) since \(5,4,3\) are in one loop.
The \(N\left ( A_{2}^{T}\right ) \) has \(m-r=6-4=2\) dimensions. Now we take the edges on each loop. Since the loop is the null space. Since there are two loops, this give us the two independent rows. The left loop has\begin{equation} \fbox{$edge\left ( 1\right ) +edge\left ( 2\right ) -edge\left ( 6\right ) =\left [ 1,1,0,0,0,-1\right ] $} \tag{1} \end{equation} Second loop has\[ \fbox{$edge\left ( 3\right ) +edge\left ( 4\right ) -edge\left ( 5\right ) =\left [ 0,0,+1,+1,-1,0\right ] $}\] In other words, we put a \(0\) for the edge that is not there and put a \(+1\) for the edge the goes one direction and \(-1\) for the edge that goes in the opposite direction. For example, in (1) we put \(1\) for edge(1) since edge(1) is in the loop. We put \(0\) for edge (3) since edge (3) is not in the loop at all. We put \(-1\) for edge(6) since it goes in the opposite direction from the others. It is arbitrary which direction is positive and which is negative, as long as one is consistent. Notice the above two basis vectors span \(N\left ( A_{2}^{T}\right ) \) and live inside \(R^{6}\) since \(m=6\) in this case.
Since \(Ax=0\) then we set up the equations from incidence matrix one for each edge as follows
If we assign one node any arbitrary value, say \(x_{k}=1\), then \(x_{j}=1\) as well. But then any node on the other side of \(x_{j}\), say \(x_{i}\) will now have value \(1\) as well. By transitivity, all other nodes will end up with the same value assigned to the first node. Hence all nodes have the same value.
For the case of a two nodes not connect. Assume the nodes are \(x_{1}\) and \(x_{4}\) and that there is no edge between them. Now assume there is an edge \(x_{1}x_{2}\) and edge \(x_{2}x_{3}\) and edge \(x_{3}x_{4}\). Since \(x_{2}=x_{1}\) since \(Ax=0\) then this implies \(x_{3}=x_{2}=x_{1}\) as well. This also implies \(x_{4}=x_{3}=x_{2}=x_{1}\) or \(x_{1}=x_{4}\) even though there is no direct edge.
Proof by contradiction: Assuming there is no loop. Hence the graph must be a spanning tree. But by definition, a spanning tree with \(N\) nodes have \(N-1\) edges. But we are given that number of edges is the same as the number of nodes. Hence the assumption is not valid, and there must be a loop, called the fundamental loop or fundamental cycle.
The fundamental theorem of linear algebra says that vectors in \(R\left ( A\right ) \) are orthogonal to vectors in \(N\left ( A^{T}\right ) \). \(Ax\) gives the vectors in \(R\left ( A\right ) \) which is the potential difference. While currents \(y\) which results in \(A^{T}y=0\) are in \(N\left ( A^{T}\right ) \). The following diagram illustrates this
Figure 2.1 is the following
The \(A_{o}\) matrix, is the incidence matrix. Since we have \(6\) edges, the matrix will have \(6\) rows. Since we have \(4\) nodes, there will be \(4\) columns. The matrix is\[ A_{o}=\begin{pmatrix} -1 & +1 & 0 & 0\\ -1 & 0 & +1 & 0\\ 0 & -1 & +1 & 0\\ 0 & -1 & 0 & +1\\ -1 & 0 & 0 & +1\\ 0 & 0 & -1 & +1 \end{pmatrix} \] Hence \(A_{o}^{T}A_{o}\) is\begin{align*} A_{o}^{T}A_{o} & =\begin{pmatrix} -1 & -1 & 0 & 0 & -1 & 0\\ 1 & 0 & -1 & -1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & -1\\ 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} -1 & +1 & 0 & 0\\ -1 & 0 & +1 & 0\\ 0 & -1 & +1 & 0\\ 0 & -1 & 0 & +1\\ -1 & 0 & 0 & +1\\ 0 & 0 & -1 & +1 \end{pmatrix} \\ & =\begin{pmatrix} 3 & -1 & -1 & -1\\ -1 & 3 & -1 & -1\\ -1 & -1 & 3 & -1\\ -1 & -1 & -1 & 3 \end{pmatrix} \end{align*}
And the \(C\) matrix is \(m\times m\) where \(m=6\) since this is the number of rows in \(A_{o}\). Hence \[ C=\begin{pmatrix} c_{1} & 0 & 0 & 0 & 0 & 0\\ 0 & c_{2} & 0 & 0 & 0 & 0\\ 0 & 0 & c_{3} & 0 & 0 & 0\\ 0 & 0 & 0 & c_{4} & 0 & 0\\ 0 & 0 & 0 & 0 & c_{5} & 0\\ 0 & 0 & 0 & 0 & 0 & c_{6}\end{pmatrix} \] Therefore\[ A_{o}^{T}CA_{o}=\begin{pmatrix} -1 & -1 & 0 & 0 & -1 & 0\\ 1 & 0 & -1 & -1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & -1\\ 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} c_{1} & 0 & 0 & 0 & 0 & 0\\ 0 & c_{2} & 0 & 0 & 0 & 0\\ 0 & 0 & c_{3} & 0 & 0 & 0\\ 0 & 0 & 0 & c_{4} & 0 & 0\\ 0 & 0 & 0 & 0 & c_{5} & 0\\ 0 & 0 & 0 & 0 & 0 & c_{6}\end{pmatrix}\begin{pmatrix} -1 & +1 & 0 & 0\\ -1 & 0 & +1 & 0\\ 0 & -1 & +1 & 0\\ 0 & -1 & 0 & +1\\ -1 & 0 & 0 & +1\\ 0 & 0 & -1 & +1 \end{pmatrix} \] Hence\[ \fbox{$A_o^TCA_o=\begin{pmatrix} c_{1}+c_{2}+c_{5} & -c_{1} & -c_{2} & -c_{5}\\ -c_{1} & c_{1}+c_{3}+c_{4} & -c_{3} & -c_{4}\\ -c_{2} & -c_{3} & c_{2}+c_{3}+c_{6} & -c_{6}\\ -c_{5} & -c_{4} & -c_{6} & c_{4}+c_{5}+c_{6}\end{pmatrix} $}\] We notice that the diagonal entry on \(A_{o}^{T}CA_{o}^{T}\) matches the sum on the rest of the row.
From problem 2.1.2, we found\[ A_{o}=\begin{pmatrix} -1 & +1 & 0 & 0\\ -1 & 0 & +1 & 0\\ 0 & -1 & +1 & 0\\ 0 & -1 & 0 & +1\\ -1 & 0 & 0 & +1\\ 0 & 0 & -1 & +1 \end{pmatrix} \] We first start by removing the last column, hence \(A=\begin{pmatrix} -1 & +1 & 0\\ -1 & 0 & +1\\ 0 & -1 & +1\\ 0 & -1 & 0\\ -1 & 0 & 0\\ 0 & 0 & -1 \end{pmatrix} \) which means \(x\) is \(3\times 1\) vector now.
We are given that \(C=\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \) and \(f=\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix} \), hence we need to solve the equilibrium equation \(-A^{T}CAx=f-A^{T}Cb\), but \(b=0\), hence this becomes\begin{align*} -A^{T}CAx & =f\\ -\begin{pmatrix} -1 & 1 & 0\\ -1 & 0 & 1\\ 0 & -1 & 1\\ 0 & -1 & 0\\ -1 & 0 & 0\\ 0 & 0 & -1 \end{pmatrix} ^{T}\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} -1 & 1 & 0\\ -1 & 0 & 1\\ 0 & -1 & 1\\ 0 & -1 & 0\\ -1 & 0 & 0\\ 0 & 0 & -1 \end{pmatrix}\begin{pmatrix} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{pmatrix} & =\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix} \\\begin{pmatrix} -3 & 1 & 1\\ 1 & -3 & 1\\ 1 & 1 & -3 \end{pmatrix}\begin{pmatrix} x_{1}\\ x_{2}\\ x_{3}\end{pmatrix} & =\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix} \end{align*}
We now solve the above by Gaussian elimination which gives\[ \fbox{$x=\begin{pmatrix} -1\\ -1\\ -1 \end{pmatrix} $}\] To solve for \(y\) we use the first equation of the equilibrium equation after elimination, which is given on page 92 of the textbook as\[\begin{pmatrix} C^{-1} & A\\ 0 & -A^{T}CA \end{pmatrix}\begin{pmatrix} y\\ x \end{pmatrix} =\begin{pmatrix} b\\ f-A^{T}Cb \end{pmatrix} \] The first equation gives\[ C^{-1}y+Ax=b \] And for \(b=0\) this becomes\begin{align*} y & =-CAx\\ & =-\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} -1 & 1 & 0\\ -1 & 0 & 1\\ 0 & -1 & 1\\ 0 & -1 & 0\\ -1 & 0 & 0\\ 0 & 0 & -1 \end{pmatrix}\begin{pmatrix} -1\\ -1\\ -1 \end{pmatrix} \end{align*}
or\[ \fbox{$y=\begin{pmatrix} 0\\ 0\\ 0\\ -1\\ -1\\ -1 \end{pmatrix} $}\] \(y\) now is the edges, it is the flow. Hence the above says that in figure 2.1 network, shown again below
That there is now flow over edges \(1,2,3\) (the outer cycle) and flow is only on the inner edges \(4,5,6\) in opposite direction shown.
The first node needs \(N-1\) edges to connect to the other \(N.\) The second node needs \(N-2\) edges to connect to the other nodes. We do not count the first one since it is already connected by now. The third node needs \(N-3\) edges, and so on. The last node needs no edges, since by the time it is reach, it already has an edge from all the others to it. Hence \begin{align*} m & =\left ( N-1\right ) +\left ( N-2\right ) +\cdots +\left ( N-N\right ) \\ & ={\displaystyle \sum \limits _{i=1}^{N}} \left ( N-i\right ) \\ & ={\displaystyle \sum \limits _{i=1}^{N}} N-{\displaystyle \sum \limits _{i=1}^{N}} i\\ & =N^{2}-\frac{1}{2}N\left ( N+1\right ) \\ & =N^{2}-\frac{1}{2}N^{2}-\frac{1}{2}N\\ & =\frac{1}{2}N^{2}-\frac{1}{2}N \end{align*}
Hence\[ m=\frac{1}{2}N\left ( N-1\right ) \]
A tree is drawn with arbitrary directions
Before grounded node 5 the \(A\) matrix is\[ A=\begin{pmatrix} -1 & +1 & 0 & 0 & 0\\ 0 & -1 & 0 & +1 & 0\\ 0 & 0 & -1 & +1 & 0\\ 0 & 0 & 0 & +1 & -1 \end{pmatrix} \] When node 5 is grounded, then column 5 is removed, now the matrix becomes\[ A=\begin{pmatrix} -1 & +1 & 0 & 0\\ 0 & -1 & 0 & +1\\ 0 & 0 & -1 & +1\\ 0 & 0 & 0 & +1 \end{pmatrix} \] And its inverse is \[ A^{-1}=\begin{pmatrix} -1 & -1 & 0 & +1\\ 0 & -1 & 0 & +1\\ 0 & 0 & -1 & +1\\ 0 & 0 & 0 & +1 \end{pmatrix} \]
\(Q=\frac{1}{2}\left ( y_{1}^{2}+\frac{1}{3}y_{2}^{2}\right ) \) and constraint \(r=y_{1}+y_{2}-8=0\) hence \(L=Q+xr\) where \(x\) here is the Lagrange multiplier. Hence\[ \fbox{$L=\frac{1}{2}\left ( y_1^2+\frac{1}{3}y_2^2\right ) +x\left ( y_1+y_2-8\right ) $}\] Therefore \begin{align*} \frac{\partial L}{\partial y_{1}} & =y_{1}+x\\ \frac{\partial L}{\partial y_{2}} & =\frac{1}{3}y_{2}+x\\ \frac{\partial L}{\partial x} & =\left ( y_{1}+y_{2}-8\right ) \end{align*}
In matrix form it becomes\begin{equation} \nabla L=\begin{pmatrix} 1 & 0 & 1\\ 0 & \frac{1}{3} & 1\\ 1 & 1 & 0 \end{pmatrix}\begin{pmatrix} y_{1}\\ y_{2}\\ x \end{pmatrix} =\begin{pmatrix} 0\\ 0\\ 8 \end{pmatrix} \tag{1} \end{equation} Solving by Gaussian elimination gives\[ \fbox{$\begin{pmatrix} y_{1}\\ y_{2}\\ x \end{pmatrix} =\begin{pmatrix} 2\\ 6\\ -2 \end{pmatrix} $}\]
We now compare (1) above to the equilibrium matrix equation given by \[\begin{pmatrix} C^{-1} & A\\ 0 & A^{T}CA \end{pmatrix}\begin{pmatrix} y\\ x \end{pmatrix} =\begin{pmatrix} b\\ f-A^{T}Cb \end{pmatrix} \] Which for \(b=0\) becomes\[\begin{pmatrix} C^{-1} & A\\ 0 & A^{T}CA \end{pmatrix}\begin{pmatrix} y\\ x \end{pmatrix} =\begin{pmatrix} 0\\ f \end{pmatrix} \] From the above, and comparing to (1) we see that \(A=\begin{pmatrix} 1\\ 1 \end{pmatrix} ,C^{-1}=\begin{pmatrix} 1 & 0\\ 0 & \frac{1}{3}\end{pmatrix} ,y=\begin{pmatrix} y_{1}\\ y_{2}\end{pmatrix} ,f=8\). Hence we first solve for \(x\)\begin{align*} A^{T}CAx & =f\\\begin{pmatrix} 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0\\ 0 & 3 \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix} x & =8\\ 4x & =8\\ x & =2 \end{align*}
Now the first equation is used to solve for \(y\)\begin{align*} C^{-1}y+Ax & =0\\ y & =CAx\\\begin{pmatrix} y_{1}\\ y_{2}\end{pmatrix} & =\begin{pmatrix} 1 & 0\\ 0 & 3 \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix} x\\\begin{pmatrix} y_{1}\\ y_{2}\end{pmatrix} & =\begin{pmatrix} 1 & 0\\ 0 & 3 \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix} 2 \end{align*}
Hence the optimal \(y\) is\[ \fbox{$\begin{pmatrix} y_{1}\\ y_{2}\end{pmatrix} =\begin{pmatrix} 2\\ 6 \end{pmatrix} $}\] Which is the same as in part(a). At this point, \(Q\) is now evaluated\begin{align*} Q_{\min } & =\frac{1}{2}\left ( y_{1}^{2}+\frac{1}{3}y_{2}^{2}\right ) \\ & =\frac{1}{2}\left ( 2^{2}+\frac{1}{3}6^{2}\right ) \\ & =8 \end{align*}
The dual quadratic is given on page 101 of the text \[ -P\left ( x\right ) =-\frac{1}{2}\left ( Ax-b\right ) ^{T}C\left ( Ax-b\right ) -x^{T}f \] And for \(b=0\) it becomes\[ -P\left ( x\right ) =-\frac{1}{2}x^{T}A^{T}CAx-x^{T}f \] But from above, \(A=\begin{pmatrix} 1\\ 1 \end{pmatrix} ,C=\begin{pmatrix} 1 & 0\\ 0 & 3 \end{pmatrix} ,f=8\) hence\begin{align*} -P\left ( x\right ) & =-\frac{1}{2}x^{T}\begin{pmatrix} 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0\\ 0 & 3 \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix} x-8x^{T}\\ & =-\frac{1}{2}x^{T}4x-8x^{T}\\ & =-2x^{T}x-8x^{T} \end{align*}
But \(x^{T}x=x^{2}\) so the above can be written as\begin{align*} -P\left ( x\right ) & =-2x^{2}-8x\\ P\left ( x\right ) & =x\left ( 2x+8\right ) \end{align*}
To find where it is maximum, since \(\frac{dP}{dx}=0=4x+8\) hence \(x=-2\). Therefore, \(-P\left ( x\right ) \) is maximized at same \(x\) where \(Q\left ( x\right ) \) is minimized.
\[ Q=\frac{1}{2}\left ( y_{1}^{2}+y_{2}^{2}+\cdots +y_{m}^{2}\right ) \] Constraints in \(y_{1}+y_{2}+\cdots +y_{m}=1\). Solving for \(y_{1}\) from the constrains and substitute the result in \(Q\). Hence\[ y_{1}=1-\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) \] And \(Q\) becomes\begin{align*} Q & =\frac{1}{2}\left ( \left [ 1-\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) \right ] ^{2}+\left ( y_{2}^{2}+\cdots +y_{m}^{2}\right ) \right ) \\ & =\frac{1}{2}\left ( 1+\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) ^{2}-2\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) +\left ( y_{2}^{2}+\cdots +y_{m}^{2}\right ) \right ) \\ & =\frac{1}{2}+\frac{1}{2}\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) ^{2}-\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) +\frac{1}{2}\left ( y_{2}^{2}+\cdots +y_{m}^{2}\right ) \end{align*}
Hence \begin{align*} \frac{\partial Q}{\partial _{y_{2}}} & =\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) -1+y_{2}=0\\ \frac{\partial Q}{\partial _{y_{3}}} & =\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) -1+y_{3}=0\\ & \vdots \\ \frac{\partial Q}{\partial _{y_{m}}} & =\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) -1+y_{m}=0 \end{align*}
The above can be written as\begin{align*} 2y_{2}+y_{3}+\cdots +y_{m} & =1\\ y_{2}+2y_{3}+\cdots +y_{m} & =1\\ & \vdots \\ y_{2}+y_{3}+\cdots +2y_{m} & =1 \end{align*}
In matrix form,\[ \fbox{$\begin{pmatrix} 2 & 1 & 1 & \cdots & 1\\ 1 & 2 & 1 & \cdots & 1\\ 1 & 1 & 2 & \cdots & 1\\ 1 & 1 & 1 & \ddots & 1\\ 1 & 1 & 1 & \cdots & 2 \end{pmatrix}\begin{pmatrix} y_{2}\\ y_{3}\\ y_{4}\\ \vdots \\ y_{m}\end{pmatrix} =\begin{pmatrix} 1\\ 1\\ 1\\ \vdots \\ 1 \end{pmatrix} $}\] Solving this gives \[ \fbox{$y_2=y_3=\cdots =y_m=\frac{1}{m}$}\] This was done by solving for \(m=3,4,5\cdots \) on the computer and seeing the result is always \(\frac{1}{m}\). Now we solve for \(y_{1}\). Since\[ y_{1}=1-\left ( y_{2}+y_{3}+\cdots +y_{m}\right ) \] Then\begin{align*} y_{1} & =1-\left ( \frac{1}{m}+\frac{1}{m}+\cdots +\frac{1}{m}\right ) \\ & =1-\left ( m-1\right ) \frac{1}{m}\\ & =1-\left ( 1-\frac{1}{m}\right ) \\ & =\frac{1}{m} \end{align*}
Therefore, all \(y_{i}\) have the value \(\frac{1}{m}\)
Now the last part is solved, which asks to solve the same problem using Lagrange multiplier. Since there is one constraint, then \(n=1\) and since there are \(m\) number of \(y\) variables, there will be \(n+m\) or \(m+1\) equations. \[ L=Q+xR \] Where \(R\) is the contraints. The above becomes\[ L=\frac{1}{2}\left ( y_{1}^{2}+y_{2}^{2}+\cdots +y_{m}^{2}\right ) +x\left ( y_{1}+y_{2}+\cdots +y_{m}-1\right ) \] Now we take the derivatives and set up the system of equations\begin{align*} \frac{\partial L}{\partial y_{1}} & =y_{1}+x=0\\ \frac{\partial L}{\partial y_{2}} & =y_{2}+x=0\\ & \vdots \\ \frac{\partial L}{\partial y_{m}} & =y_{m}+x=0\\ \frac{\partial L}{\partial x} & =\left ( y_{1}+y_{2}+\cdots +y_{m}-1\right ) =0 \end{align*}
In matrix form the above is\[ \fbox{$\begin{pmatrix} 1 & 0 & 0 & \cdots & 1\\ 0 & 1 & 0 & \cdots & 1\\ 0 & 0 & 1 & \cdots & 1\\ 0 & 0 & 0 & \ddots & 1\\ 1 & 1 & 1 & \cdots & 0 \end{pmatrix}\begin{pmatrix} y_{1}\\ y_{2}\\ y_{3}\\ \vdots \\ x \end{pmatrix} =\begin{pmatrix} 0\\ 0\\ 0\\ \vdots \\ 1 \end{pmatrix} $}\] Solving this also gives the same answer as above, which is \[ y_{i}=\frac{1}{m}\] and the Lagrange multipler is found, using any of the above equation, such as \(y_{1}+x=0\) to be\[ \fbox{$x=-\frac{1}{m}$}\]
We want to maximize \(Q=4y_{1}+4y_{2}\) subject to \(y_{1}^{2}+4y_{2}^{2}=1\). Hence\begin{align*} L & =Q+x\left ( y_{1}^{2}+4y_{2}^{2}-1\right ) \\ & =4y_{1}+4y_{2}+x\left ( y_{1}^{2}+4y_{2}^{2}-1\right ) \end{align*}
And \begin{align} \frac{\partial L}{\partial y_{1}} & =4+2xy_{1}=0\tag{1}\\ \frac{\partial L}{\partial y_{2}} & =4+8xy_{2}=0\tag{2}\\ \frac{\partial L}{\partial x} & =y_{1}^{2}+4y_{2}^{2}-1=0 \tag{3} \end{align}
Or\begin{align} y_{1} & =\frac{-2}{x}\tag{1}\\ y_{2} & =\frac{-1}{2x}\tag{2}\\ y_{1}^{2}+4y_{2}^{2} & =1 \tag{3} \end{align}
From (1),(2) we see that \(y_{1}=4y_{2}\). Substituting in (3) gives\begin{align*} \left ( 4y_{2}\right ) ^{2}+4y_{2}^{2} & =1\\ 16y_{2}^{2}+4y_{2}^{2} & =1\\ y_{2} & =\pm \sqrt{\frac{1}{20}} \end{align*}
Hence \[ y_{1}=\pm \sqrt{\frac{16}{20}}=\pm \sqrt{\frac{4}{5}}\] So the corners are \(\left ( \pm \sqrt{\frac{4}{5}},\pm \sqrt{\frac{1}{20}}\right ) \). Here is a plot of the ellipse showing the 4 corners given by the above solution to verify
From the duality statement on page 100 of the text, we can complete this sentence similarly by saying
The minimum distance to the surface \(A^{T}y=f\) equals the maximum distance to the hyperplanes which go through those hyperplanes.