Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

Section 12.5 Some Applications

A large and varied number of applications involve computations of powers of matrices. These applications can be found in science, the social sciences, economics, engineering, and, many other areas where mathematics is used. We will consider a few diverse examples the mathematics behind these applications here.
🔗

Subsection 12.5.1 Matrix Analysis of Markov Chains

In Markov Chains we introduced the idea of a Markov Chain. The movement in such a process can be visualized with a transition graph, Computation of probabilities related to such a process is often done using matrix algebra. The basic component in the computations is the transition matrix for the process.
🔗

Definition 12.5.1. Transition Matrix.

Given a Markov Chain with states \(s_1, s_2, \dots, s_n\text{,}\) the transition matrix for the process is the \(n \times n\) matrix \(T\) where \(T_{i,j}\) is the probability that if the process is in state \(s_i\text{,}\) its next state is \(s_j\text{.}\)
🔗
🔗
The ordering of states can be arbitrary, but is most convenient to list the absorbins states of the process, the ones that are permanently entered, last. The transition matrix for the tennis game process with states ordered Ad-In, Deuce, Ad-Out, Hold, Break is
🔗
\begin{equation*} T=\left( \begin{array}{ccccc} 0 & 0.4 & 0 & 0.6 & 0 \\ 0.6 & 0 & 0.4 & 0 & 0 \\ 0 & 0.6 & 0 & 0 & 0.4 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right). \end{equation*}
🔗
Representing a Markov chain by its transition matrix makes it easy to compute probabilities associated with it. For example, we might want to know the probability that if the game is in Deuce that after two points have been played it is back in Deuce. We can reason that to return to Deuce the process can go from Deuce to Ad-In and back to Deuce. This happens with probability
🔗
\begin{equation*} T_{2,1}\cdot T_{1,2} =0.6 \cdot 0.4 = 0.24. \end{equation*}
🔗
The other way to return to Deuce is to go to Ad-Out and then back to Deuce. This happens with probability
\begin{equation*} T_{2,3}\cdot T_{3,2} =0.4 \cdot 0.6 = 0.24. \end{equation*}
Since these paths in the graph are mutually exclusive (they can’t both happen), the probability of being in Deuce after two points is the sum 0.48. The two products we added here are the nonzero terms of the innner product of the second row of \(T\) with the second column of \(T\text{.}\) If we compute the \(T^2\text{,}\) we get this result in the second row, second column. But the whole matrix gives us the transition probabilities between any pair of states after two points have been played. Here is the whole matrix:
\begin{equation*} T^2=\left( \begin{array}{ccccc} 0.24 & 0. & 0.16 & 0.6 & 0. \\ 0. & 0.48 & 0. & 0.36 & 0.16 \\ 0.36 & 0. & 0.24 & 0. & 0.4 \\ 0. & 0. & 0. & 1. & 0. \\ 0. & 0. & 0. & 0. & 1. \\ \end{array} \right). \end{equation*}
🔗
In general, the \(n^{th}\) power of \(T\) will give us the probabilities after \(n\) points have been played. For example, starting at Deuce the probabiity that the server will have held serve is \(0.674667\) while a service break would have taken place with probability \(0.299852\text{,}\) The likelihood that the game would still be undecided is \(0.0254804\text{.}\)
🔗
To summarize,
🔗

Proof.

(Proof by induction) Assume there are \(m\) states in a Markov chain. Let \(p(i,j,n)\) be the probability that starting in state \(i\text{,}\) the process will be in state \(j\) after \(n\) steps. By the definition of \(T\text{,}\) \(T_{i,j} = p(i,j,1)\) and so the basis is trivial.
🔗
Assume the theorem is true for some \(n \geq 1\text{.}\) We observe that in the process is to end in state \(j\) after \(n+1\) steps, it could enter it from any of the \(n\) states and so
\begin{equation*} \begin{split} p(i,j,n+1)&=\sum_{k=1}^m p(i,k,n)\cdot p(k,j,1)\\ &=\sum_{k=1}^m T^n_{i,k}\cdot T_{k,j}\\ &=T^{n+1}_{i,j} \end{split} \end{equation*}
🔗
🔗

Example 12.5.3. A Bike Share Program.

(suggested by Kaily Burke) Consider a citywide bike share program with three stations A, B, and C. Bikes borrowed from one station may be returned to any station by the end of each night. Assuming all bikes borrowed on a certain day are returned at night, we observe from past data the following probabilities of each bike’s subsequent state:
  • From Station A: \(30\%\) of bikes return to Station A, \(50\%\) return to station B, \(20\%\) return to Station C.
    🔗
    🔗
  • From Station B: \(10\%\) return to station A, \(60\%\) to station B, \(30\%\) to station C.
    🔗
    🔗
  • From Station C: \(10\%\) return to station A, \(10\%\) to station B, \(80\%\) to station C.
    🔗
    🔗
🔗
Unlike the tennis example, this process every state can be reached from every other state. These are called transition states. The natural question to ask here is whether the distribution of bikes tend toward a steady state. This, in fact, is true. No matter where a bike starts, the probability that it is in any of the three stations will be largely independent of the starting state.
🔗
The transition matrix for this Markov chain with the ordering of states A, B, C is
\begin{equation*} B=\left( \begin{array}{ccc} 0.3 & 0.5 & 0.2 \\ 0.1 & 0.6 & 0.3 \\ 0.1 & 0.1 & 0.8 \\ \end{array} \right) \end{equation*}
If we compute the seventh power of this matrix, we get the probabilities after a week. For example, the first row give the probabilities of being in states A, B and C after a week if the initial state is A. Notice that these probabilities are not very different if the initial state is B or C.
🔗
We don’t need to perform these calculations to get exact steady-state probabilities. We need only look to the one of the left eigenvectors of the transition matrix, as indicated in the following theorem, which we state here without proof.
🔗
We first examine the left eigenvectors of our matrix and see that 1 is first eigenvalue and it has an eigenspace of dimension one and a basis vector having positive entries.
🔗
We extract the first eigenvector and divide by the sum of its entries to get a probability vector. Recall that SageMath objects are indexed starting a 0.
🔗
We can verify that if the probabilities are in equilibrium - they stay the same if we apply them to the transition matrix.
🔗
🔗
🔗

Subsection 12.5.2 Diagonalization

We begin by developing a helpful technique for computing \(A^m\text{,}\) \(m > 1\text{.}\) If \(A\) can be diagonalized, then there is a matrix \(P\) such that \(P^{-1}A P = D\text{,}\) where \(D\) is a diagonal matrix and
\begin{gather} A^m= P D^m P^{-1} \textrm{ for all } m\geq 1\tag{12.5.1} \end{gather}
🔗
The proof of this identity was an exercise in Section 5.4. The condition that \(D\) be a diagonal matrix is not necessary but when it is, the calculation on the right side is particularly easy to perform. Although the formal proof is done by induction, the reason why it is true is easily seen by writing out an example such as \(m=3\text{:}\)
\begin{equation*} \begin{split} A^3 & = \left(P D P^{-1}\right)^3\\ & =\left(P D P^{-1}\right)\left(P D P^{-1}\right)\left(P D P^{-1}\right)\\ &= P D \left(P^{-1}P\right) D \left(P^{-1}P \right)D P^{-1}\quad\textrm{by associativity of matrix multiplication}\\ &= P D I D I D P^{-1}\\ &= P D D D P^{-1}\\ &= P D^3 P^{-1}\\ \end{split} \end{equation*}
🔗

Example 12.5.5. Application to Recursion: Matrix Computation of the Fibonnaci Sequence.

Consider the computation of terms of the Fibonnaci Sequence. Recall that \(F_0= 1, F_1= 1\) and \(F_k= F_{k-1}+F_{k-2}\) for \(k\geq 2\text{.}\)
🔗
In order to formulate the calculation in matrix form, we introduced the “dummy equation” \(F_{k-1}= F_{k-1}\) so that now we have two equations
\begin{equation*} \begin{array}{c} F_k= F_{k-1}+F_{k-2}\\ F_{k-1}= F_{k-1}\\ \end{array} \end{equation*}
If \(A = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right)\text{,}\) these two equations can be expressed in matrix form as
\begin{equation*} \begin{split} \left( \begin{array}{c} F_k \\ F_{k-1} \\ \end{array} \right) &=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right)\left( \begin{array}{c} F_{k-1} \\ F_{k-2} \\ \end{array} \right) \quad\textrm{ if } k\geq 2\\ &= A \left( \begin{array}{c} F_{k-1} \\ F_{k-2} \\ \end{array} \right)\\ &= A^2\left( \begin{array}{c} F_{k-2} \\ F_{k-3} \\ \end{array} \right) \quad\textrm{ if } k\geq 3\\ & etc.\\ \end{split} \end{equation*}
We can use induction to prove that if \(k\geq 2\text{,}\)
\begin{equation*} \left( \begin{array}{c} F_k \\ F_{k-1} \\ \end{array} \right)=A^{k-1} \left( \begin{array}{c} 1 \\ 1 \\ \end{array} \right) \end{equation*}
🔗
Next, by diagonalizing \(A\) and using the fact that \(A^{m }= P D^m P^{-1}\text{.}\) we can show that
\begin{equation*} F_k= \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^k- \left(\frac{1-\sqrt{5}}{2}\right)^k\right) \end{equation*}
🔗
Some comments on this example:
  1. An equation of the form \(F_k = a F_{k-1} + b F_{k-2}\) , where \(a\) and \(b\) are given constants, is referred to as a linear homogeneous second-order difference equation. The conditions \(F_0=c_0\) and \(F_1= c_1\) , where \(c_1\) and \(c_2\) are constants, are called initial conditions. Those of you who are familiar with differential equations may recognize that this language parallels what is used in differential equations. Difference (aka recurrence) equations move forward discretely; that is, in a finite number of positive steps. On the other hand, a differential equation moves continuously; that is, takes an infinite number of infinitesimal steps.
    🔗
    🔗
  2. A recurrence relationship of the form \(S_k = a S_{k-1} + b\text{,}\) where \(a\) and \(b\) are constants, is called a first-order difference equation. In order to write out the sequence, we need to know one initial condition. Equations of this type can be solved similarly to the method outlined in the example by introducing the superfluous equation \(1 =0\cdot F_{k-1}+1\) to obtain in matrix equation:
    \begin{equation*} \left( \begin{array}{c} F_k \\ 1 \\ \end{array} \right)=\left( \begin{array}{cc} a & b \\ 0 & 1 \\ \end{array} \right)\left( \begin{array}{c} S_{k-1} \\ 1 \\ \end{array} \right)\textrm{ }\Rightarrow \left( \begin{array}{c} F_k \\ 1 \\ \end{array} \right)=\left( \begin{array}{cc} a & b \\ 0 & 1 \\ \end{array} \right)^k\left( \begin{array}{c} F_0 \\ 1 \\ \end{array} \right) \end{equation*}
    🔗
    🔗
🔗
🔗
🔗

Subsection 12.5.3 Path Counting

In the next example, we apply the following theorem, which can be proven by induction.
🔗

Example 12.5.7. Counting Paths with Diagonalization.

Consider the graph in Figure 12.5.8.
🔗
described in detail following the image
Counting Numbers of Paths
🔗
Figure 12.5.8. Counting Numbers of Paths
🔗
As we saw in Section 9.2, the adjacency matrix of this graph is \(A=\left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{array} \right)\text{.}\)
🔗
Recall that \(A^k\) is the adjacency matrix of the relation \(r^k\text{,}\) where \(r\) is the relation \(\{(a, a), (a, b), (b, a), (b, c), (c, b), (c, c)\}\) of the above graph. Also recall that in computing \(A^k\text{,}\) we used Boolean arithmetic. What happens if we use “regular” arithmetic? If we square \(A\) we get \(A^2 = \left( \begin{array}{ccc} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\ \end{array} \right)\)
🔗
How can we interpret this? We note that \(A_{33} = 2\) and that there are two paths of length two from \(c\) (the third node) to \(c\text{.}\) Also, \(A_{13} = 1\text{,}\) and there is one path of length 2 from \(a\) to \(c\text{.}\) The reader should verify these claims by examining the graph.
🔗
How do we compute \(A^k\) for possibly large values of \(k\text{?}\) From the discussion at the beginning of this section, we know that \(A^k= P D^kP^{-1}\) if \(A\) is diagonalizable. We leave to the reader to show that \(\lambda = 1, 2,\textrm{ and } -1\) are eigenvalues of \(A\) with eigenvectors
\begin{equation*} \left( \begin{array}{c} 1 \\ 0 \\ -1 \\ \end{array} \right),\left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array} \right), \textrm{ and } \left( \begin{array}{c} 1 \\ -2 \\ 1 \\ \end{array} \right) \end{equation*}
🔗
Then
\begin{equation*} A^k= P \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 2^k & 0 \\ 0 & 0 & (-1)^k \\ \end{array} \right)P^{-1} \end{equation*}
where \(P=\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & -2 \\ -1 & 1 & 1 \\ \end{array} \right)\) and \(P^{-1}=\left( \begin{array}{ccc} \frac{1}{2} & 0 & -\frac{1}{2} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{6} & -\frac{1}{3} & \frac{1}{6} \\ \end{array} \right)\)
🔗
See Exercise 12.5.6.5 of this section for the completion of this example.
🔗
🔗
🔗

Subsection 12.5.4 Matrix Calculus

Example 12.5.9. Matrix Calculus - Exponentials.

Those who have studied calculus recall that the Maclaurin series is a useful way of expressing many common functions. For example, \(e^x=\sum _{k=0}^{\infty } \frac{x^k}{k!}\text{.}\) Indeed, calculators and computers use these series for calculations. Given a polynomial \(f(x)\text{,}\) we defined the matrix-polynomial \(f(A)\) for square matrices in Chapter 5. Hence, we are in a position to describe \(e^A\) for an \(n \times n\) matrix \(A\) as a limit of polynomials, the partial sums of the series. Formally, we write
\begin{equation*} e^A= I + A + \frac{A^2}{2! }+ \frac{A^3}{3!}+ \cdots = \sum _{k=0}^{\infty } \frac{A^k}{k!} \end{equation*}
🔗
Again we encounter the need to compute high powers of a matrix. Let \(A\) be an \(n\times n\) diagonalizable matrix. Then there exists an invertible \(n\times n\) matrix \(P\) such that \(P^{-1}A P = D\text{,}\) a diagonal matrix, so that
\begin{equation*} \begin{split} e^A &=e^{P D P^{-1} }\\ & =\sum _{k=0}^{\infty } \frac{\left(P D P^{-1}\right)^k}{k!} \\ & = P \left(\sum _{k=0}^{\infty } \frac{ D^k}{k!}\right)P^{-1} \end{split} \end{equation*}
🔗
The infinite sum in the middle of this final expression can be easily evaluated if \(D\) is diagonal. All entries of powers off the diagonal are zero and the \(i^{\textrm{ th}}\) entry of the diagonal is
\begin{equation*} \left(\sum _{k=0}^{\infty } \frac{ D^k}{k!}\right){}_{i i}=\sum _{k=0}^{\infty } \frac{ D_{i i}{}^k}{k!}= e^{D_{ii}} \end{equation*}
🔗
For example, if \(A=\left( \begin{array}{cc} 2 & 1 \\ 2 & 3 \\ \end{array} \right)\text{,}\) the first matrix we diagonalized in Section 12.3, we found that \(P =\left( \begin{array}{cc} 1 & 1 \\ -1 & 2 \\ \end{array} \right)\) and \(D= \left( \begin{array}{cc} 1 & 0 \\ 0 & 4 \\ \end{array} \right)\text{.}\)
🔗
Therefore,
\begin{equation*} \begin{split} e^A &=\left( \begin{array}{cc} 1 & 1 \\ -1 & 2 \\ \end{array} \right) \left( \begin{array}{cc} e & 0 \\ 0 & e^4 \\ \end{array} \right) \left( \begin{array}{cc} \frac{2}{3} & -\frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} \\ \end{array} \right)\\ &= \left( \begin{array}{cc} \frac{2 e}{3}+\frac{e^4}{3} & -\frac{e}{3}+\frac{e^4}{3} \\ -\frac{2 e}{3}+\frac{2 e^4}{3} & \frac{e}{3}+\frac{2 e^4}{3} \\ \end{array} \right)\\ & \approx \left( \begin{array}{cc} 20.0116 & 17.2933 \\ 34.5866 & 37.3049 \\ \end{array} \right) \end{split} \end{equation*}
🔗
🔗

Remark 12.5.10.

Many of the ideas of calculus can be developed using matrices. For example, if \(A(t) = \left( \begin{array}{cc} t^3 & 3 t^2+8t \\ e^t & 2 \\ \end{array} \right)\) then \(\frac{d A(t)}{d t}=\left( \begin{array}{cc} 3 t^2 & 6 t+8 \\ e^t & 0 \\ \end{array} \right)\)
🔗
Many of the basic formulas in calculus are true in matrix calculus. For example,
\begin{equation*} \frac{d (A(t)+B(t))}{d t} = \frac{d A(t)}{d t}+ \frac{d B(t)}{d t} \end{equation*}
and if \(A\) is a constant matrix,
\begin{equation*} \frac{d e^{A t}}{d t}= A e^{A t} \end{equation*}
🔗
Matrix calculus can be used to solve systems of differential equations in a similar manner to the procedure used in ordinary differential equations.
🔗
🔗
🔗

Subsection 12.5.5 SageMath Note - Matrix Exponential

Sage’s matrix exponential method is exp.
🔗
🔗

Exercises 12.5.6 Exercises

1.

  1. Write out all the details of Example 12.5.5 to show that the formula for \(F_k\) given in the text is correct.
    🔗
    🔗
  2. Use induction to prove the assertion made in the example that \(\left( \begin{array}{c} F_k \\ F_{k-1} \\ \end{array} \right)=A^{k-1} \left( \begin{array}{c} 1 \\ 1 \\ \end{array} \right)\)
    🔗
    🔗
🔗
🔗

3.

Solve \(S(k) = 5S(k - 1) + 4\text{,}\) with \(S(0) = 0\text{,}\) using the method of this section.
🔗
🔗

4.

How many paths are there of length 6 from vertex 1 to vertex 3 in Figure 12.5.11? How many paths from vertex 2 to vertex 2 of length 6 are there?
🔗
described in detail following the image
Graph for exercise 4
🔗
Figure 12.5.11. Graph for exercise 4
🔗
Hint.
The characteristic polynomial of the adjacency matrix is \(\lambda ^4 - 4 \lambda^2\text{.}\)
🔗
🔗
🔗

5.

Regarding Example 12.5.7,
  1. Use matrices to determine the number of paths of length 1 that exist from vertex \(a\) to each of the vertices in the given graph. Verify using the graph. Do the same for vertices \(b\) and \(c\text{.}\)
    🔗
    🔗
  2. Verify all the details provided in the example.
    🔗
    🔗
  3. Use matrices to determine the number of paths of length 4 there between each pair of nodes in the graph. Verify your results using the graph.
    🔗
    🔗
🔗
Answer.
  1. Since \(A=A^1= \left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{array} \right)\text{,}\) there are 0 paths of length 1 from: node c to node a, node b to node b, and node a to node c; and there is 1 path of length 1 for every other pair of nodes.
    🔗
    🔗
  2. The characteristic polynomial is \(\lvert A-c I\rvert = \left| \begin{array}{ccc} 1-c & 1 & 0 \\ 1 & -c & 1 \\ 0 & 1 & 1-c \\ \end{array} \right| = -c^3+2 c^2+c-2\)
    🔗
    Solving the characteristic equation \(-c^3+2 c^2+c-2=0\) we find solutions 1, 2, and -1.
    🔗
    If \(c=1\text{,}\) we find the associated eigenvector by finding a nonzero solution to \(\left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & -1 & 1 \\ 0 & 1 & 0 \\ \end{array} \right)\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)=\left( \begin{array}{c} 0 \\ 0 \\ 0 \\ \end{array} \right)\) One of these, which will be the first column of \(P\text{,}\) is \(\left( \begin{array}{c} 1 \\ 0 \\ -1 \\ \end{array} \right)\)
    🔗
    If \(c=2\text{,}\) the system \(\left( \begin{array}{ccc} -1 & 1 & 0 \\ 1 & -2 & 1 \\ 0 & 1 & -1 \\ \end{array} \right)\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)=\left( \begin{array}{c} 0 \\ 0 \\ 0 \\ \end{array} \right)\) yields eigenvectors, including \(\left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array} \right)\text{,}\) which will be the second column of \(P\text{.}\)
    🔗
    If \(c = -1\text{,}\) then the system determining the eigenvectors is \(\left( \begin{array}{ccc} 2 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \\ \end{array} \right)\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)=\left( \begin{array}{c} 0 \\ 0 \\ 0 \\ \end{array} \right)\) and we can select \(\left( \begin{array}{c} 1 \\ -2 \\ 1 \\ \end{array} \right)\text{,}\) although any nonzero multiple of this vector could be the third column of \(P\text{.}\)
    🔗
    🔗
  3. Assembling the results of part (b) we have \(P=\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & -2 \\ -1 & 1 & 1 \\ \end{array} \right)\) .
    🔗
    \begin{equation*} \begin{split} A^4 & = P \left( \begin{array}{ccc} 1^4 & 0 & 0 \\ 0 & 2^4 & 0 \\ 0 & 0 & (-1)^{4 } \\ \end{array} \right)P^{-1}= P \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 16 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)P^{-1}\\ &=\left( \begin{array}{ccc} 1 & 16 & 1 \\ 0 & 16 & -2 \\ -1 & 16 & 1 \\ \end{array} \right)\left( \begin{array}{ccc} \frac{1}{2} & 0 & -\frac{1}{2} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{6} & -\frac{1}{3} & \frac{1}{6} \\ \end{array} \right)\\ &=\left( \begin{array}{ccc} 6 & 5 & 5 \\ 5 & 6 & 5 \\ 5 & 5 & 6 \\ \end{array} \right)\\ \end{split} \end{equation*}
    🔗
    Hence there are five different paths of length 4 between distinct vertices, and six different paths that start and end at the same vertex. The reader can verify these facts from Figure 12.5.8
    🔗
    🔗
🔗
🔗
🔗

6.

Let \(A =\left( \begin{array}{cc} 2 & -1 \\ -1 & 2 \\ \end{array} \right)\)
  1. Find \(e^A\)
    🔗
    🔗
  2. Recall that \(\sin x = \sum _{k=0}^{\infty } \frac{(-1)^k x^k}{(2 k+1)!}\) and compute \(\sin A\text{.}\)
    🔗
    🔗
  3. Formulate a reasonable definition of the natural logarithm of a matrix and compute \(\ln A\text{.}\)
    🔗
    🔗
🔗
🔗

7.

We noted in Chapter 5 that since matrix algebra is not commutative under multiplication, certain difficulties arise. Let \(A=\left( \begin{array}{cc} 1 & 1 \\ 0 & 0 \\ \end{array} \right)\) and \(B=\left( \begin{array}{cc} 0 & 0 \\ 0 & 2 \\ \end{array} \right)\text{.}\)
  1. Compute \(e^A\text{,}\) \(e^B\text{,}\) and \(e^{A+B}\text{.}\) Compare \(e^A e^{B}\text{,}\) \(e^B e^A\) and \(e^{A+B}\) .
    🔗
    🔗
  2. Show that if \(\pmb{0}\) is the \(2\times 2\) zero matrix, then \(e^{\pmb{0}}= I\text{.}\)
    🔗
    🔗
  3. Prove that if \(A\) and \(B\) are two matrices that do commute, then \(e^{A+B}=e^Ae^B\text{,}\) thereby proving that \(e^A\) and \(e^B\) commute.
    🔗
    🔗
  4. Prove that for any matrix \(A\text{,}\) \(\left(e^A\right)^{-1}= e^{-A}\text{.}\)
    🔗
    🔗
🔗
Answer.
  1. \(e^A=\left( \begin{array}{cc} e & e \\ 0 & 0 \\ \end{array} \right)\) , \(e^B=\left( \begin{array}{cc} 0 & 0 \\ 0 & e^2 \\ \end{array} \right)\text{,}\) and \(e^{A+B}=\left( \begin{array}{cc} e & e^2-e \\ 0 & e^2 \\ \end{array} \right)\)
    🔗
    🔗
  2. Let \(\pmb{0}\) be the zero matrix, \(e^{\pmb{0}}=I + \pmb{0}+\frac{\pmb{0}^2}{2}+\frac{\pmb{0}^3}{6}+\ldots =I\) .
    🔗
    🔗
  3. Assume that \(A\) and \(B\) commute. We will examine the first few terms in the product \(e^A e^B\text{.}\) The pattern that is established does continue in general. In what follows, it is important that \(A B = B A\text{.}\) For example, in the last step, \((A+B)^2\) expands to \(A^2+A B + B A + B^2\text{,}\) not \(A^2+ 2 A B + B^2\text{,}\) if we can’t assume commutativity.
    \begin{equation*} \begin{split} e^Ae^B &= \left(\sum _{k=0}^{\infty } \frac{A^k}{k!}\right) \left(\sum _{k=0}^{\infty } \frac{B^k}{k!}\right)\\ & =\left(I + A+\frac{A^2}{2}+ \frac{A^3}{6}+ \cdots \right)\left(I +B+\frac{B^2}{2}+ \frac{B^3}{6}+ \cdots \right)\\ &= I + A + B+ \frac{A^2}{2}+ A B + \frac{B^2}{2}+\frac{A^3}{6}+ \frac{A^2B}{2}+\frac{A B^2}{2}+ \frac{B^3}{6}+\cdots \\ &= I + (A+B) + \frac{1}{2}\left(A^2+ 2 A B + B^2\right)+ \frac{1}{6}\left(A^3+ 3A^2B+ 3A B^2+ B^3\right)+\cdots \\ &=I + (A+B)+ \frac{1}{2}(A+B)^2+ \frac{1}{6}(A+B)^3+\cdots \\ & =e^{A+B}\\ \end{split} \end{equation*}
    🔗
    🔗
  4. Since \(A\) and \(-A\) commute, we can apply part d;
    \begin{equation*} e^Ae^{-A} = e^{A+(-A)} =e^{\pmb{0}} =I \end{equation*}
    🔗
    🔗
🔗
🔗
🔗

8.

Another observation for adjacency matrices: For the matrix in Example 12.5.7, note that the sum of the elements in the row corresponding to the node \(a\) (that is, the first row) gives the outdegree of \(a\text{.}\) Similarly, the sum of the elements in any given column gives the indegree of the node corresponding to that column.
🔗
described in detail following the image
Graph for exercise 8
🔗
Figure 12.5.12. Graph for exercise 8
🔗
  1. Using the matrix \(A\) of Example 12.5.7, find the outdegree and the indegree of each node. Verify by the graph.
    🔗
    🔗
  2. Repeat part (a) for the directed graphs in Figure 12.5.12.
    🔗
    🔗
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext