Linear algebra (Osnabrück 2024-2025)/Part II/Exercise sheet 54

Exercises

Exercise

Let ${}M$ be a column stochastic matrix. Show that the image of every distribution vector is again a distribution vector.

Exercise

Discuss, in the situation of Example 54.2 , the special cases

1. ${}p_{1}=1$ and ${}p_{2}=1$,
2. ${}p_{1}=1$ and ${}p_{2}=0$,
3. ${}p_{1}=0$ and ${}p_{2}=1$,
4. ${}p_{1}=0$ and ${}p_{2}=0$,
5. ${}p_{1}=p_{2}$,
6. ${}p_{1}=p_{2}={\frac {1}{2}}$.

Exercise

Find an eigenvector for the matrix

${\begin{pmatrix}p_{1}&p_{2}\\1-p_{1}&1-p_{2}\end{pmatrix}}$

with

${}0\leq p_{1},p_{2}\leq 1\,$

to the eigenvalue ${}p_{1}-p_{2}$. Is it an eigendistribution?

Exercise

We consider the column stochastic matrix

${\begin{pmatrix}m&0&1-r\\1-p&q&0\\0&1-q&r\end{pmatrix}}$

with ${}0\leq p,q,r\leq 1$.

a) Compute the eigenvalues of the matrix.

b) Compute an eigendistribution.

Exercise

We consider the stochastic matrix where every column equals ${}{\begin{pmatrix}p_{1}\\p_{2}\\\vdots \\p_{n}\end{pmatrix}}$. Determine the eigendistribution and a basis of the kernel of this matrix.

Exercise

Interpret a permutation matrix as a stochastic matrix. What are the eigendistributions?

Exercise

What does it mean for a column stochastic matrix that in one row all entries are positive, and what does it mean that in one column all entries are positive?

Exercise

Show that the set of all column stochastic matrices is contained in the sphere of radius ${}1$ with respect to the column sum norm. Does equality hold?

Exercise

Recall that the two concepts, a relation on a set ${}M$ (in the sense of definition, where the two sets are supposed to be equal), and a directed graph (in the sense of an arrow diagram, where at most one arrow goes from one point to another) are mathematically equivalent.

Exercise

Establish the adjacency matrix of the directed graph on the right.

Exercise

What particular properties does the adjacency matrix of an equivalence relation has?

Exercise

Express, for the group ${}C$ of the UEFA Euro 2016, the winning structure as a relation, as an arrow diagram (a directed graph), and by an adjacency matrix.

Exercise

Establish for the group ${}C$ of the UEFA Euro 2016 the stochastic matrix that arises from the extended adjacency matrix of the winning structure, where in the diagonal we put a ${}1$ everywhere (to avoid a zero column). What is the corresponding eigendistribution?

Exercise

In a group with ${}n$ football teams (for example, a group in the UEFA European Football Championship), every team plays very every other team; for a victory, the team gets 3 points, for a tie, the team gets 1 point, and for a loss, the team gets no point. The results are documented in an ${}n\times n$-matrix in such a way that the entry at the position ${}(M,N)$ say how many points the team ${}M$ has obtained in the game versus ${}N$ (at the position ${}(M,M)$, we put ${}0$). What vector arises when we apply this matrix to the vector ${}{\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}$? Establish this matrix for the group ${}C$ of the UEFA Euro 2016.

Exercise

For students of various subjects, we have observed statistically the following movements from one semester to the next semester.

a) A student of mathematics sticks with a percentage of ${}60\%$ to mathematics, he or she changes with a percentage of ${}10\%$ to philosophy, with a percentage of ${}10\%$to physics, and takes with a percentage of ${}20\%$ a semester off.

b) A student of philosophy sticks with a percentage of ${}40\%$ to philosophy, changes with a percentage of ${}10\%$ to mathematics, with a percentage of ${}20\%$ to physics, and takes with a percentage of ${}30\%$ a semester off.

c) A student of physics sticks with a percentage of ${}50\%$ to physics, changes with a percentage of ${}30\%$ to mathematics, and takes with a percentage of ${}20\%$ a semester off.

d) Someone who takes a semester off sticks with a percentage of ${}40\%$ to this, and changes with a percentage of ${}20\%$ to either mathematics, philosophy, or physics.

1. Establish a stochastic matrix representing these movements.
2. Which matrix describes the movement from the third to the sixth semester?
3. Suppose that in the first semester, the students start with the same probability with the subjects mathematics, philosophy, or physics. How large is the proportion of students who take a semester off in their forth semester?

Exercise

Compute the first five iterations of the column stochastic matrix

${\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{3}}\\{\frac {1}{2}}&{\frac {2}{3}}\end{pmatrix}}$

for the initial distributions

${\begin{pmatrix}1\\0\end{pmatrix}},\,{\begin{pmatrix}0\\1\end{pmatrix}}{\text{ and }}{\begin{pmatrix}{\frac {1}{4}}\\{\frac {3}{4}}\end{pmatrix}}.$

Exercise

Compute the first four iterations of the column stochastic matrix

${\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}&{\frac {1}{3}}\\{\frac {1}{3}}&{\frac {1}{2}}&{\frac {1}{3}}\\{\frac {1}{6}}&0&{\frac {1}{3}}\end{pmatrix}}$

for the initial distribution

${\begin{pmatrix}1\\0\\0\end{pmatrix}}.$

Exercise

Compute the eigendistribution of the column stochastic matrix

${\begin{pmatrix}{\frac {1}{6}}&{\frac {5}{8}}&0\\{\frac {1}{2}}&0&{\frac {1}{3}}\\{\frac {1}{3}}&{\frac {3}{8}}&{\frac {2}{3}}\end{pmatrix}}.$

Exercise

We consider the column stochastic matrix

${}M={\begin{pmatrix}{\frac {1}{3}}&{\frac {1}{4}}\\{\frac {2}{3}}&{\frac {3}{4}}\end{pmatrix}}\,.$

Determine the minimal ${}n$ such that in the ${}n$-th power ${}M^{n}$, the difference between the first and the second column is ${}\leq {\frac {1}{1000}}$ with respect to the maximum norm of ${}\mathbb {R} ^{2}$.

Exercise

Let a circle with six (equidistant) points be given, denoted by ${}1,2,3,4,5,6$. We look at a movement process where the probabilities to stay at the current position and to change to the neighbor on the left or on the right equal ${}{\frac {1}{3}}$. Establish the corresponding stochastic matrix, and compute the eigendistribution(s).

Exercise

Let ${}M$ be a column stochastic ${}n\times n$-matrix. Show directly that ${}1$ is an eigenvalue of ${}M$.

Exercise

Under what conditions does for real numbers ${}a_{1},a_{2},\ldots ,a_{n}$ the equality

${}\vert {\sum _{i=1}^{n}a_{i}}\vert =\sum _{i=1}^{n}\vert {a_{i}}\vert \,$

hold?

Exercise

Let ${}M$ be a ${}n\times n$-column stochastic matrix, and set

${}U={\left\{{\begin{pmatrix}u_{1}\\\vdots \\u_{n}\end{pmatrix}}\mid \sum _{i=1}^{n}u_{i}=0\right\}}\subseteq \mathbb {R} ^{n}\,.$

a) Show that ${}U$ is invariant under ${}M$.

b) Show that the restriction ${}M{|}_{U}$ is stable.

c) Show that the restriction ${}M{|}_{U}$ is not necessarily asymptotically stable.

Exercise

Let ${}M$ be a column stochastic matrix where at least one row has only positive entries. Show that the sequence ${}M^{n}$ converges to a matrix ${}N$ where all columns are equal.

Exercise

We want to establish statements about the determinant of a column stochastic ${}d\times d$-matrix.

1. Show that the determinant of a column stochastic matrix ${}M$ fulfills the relation

   ${}\vert {\det M}\vert \leq 1\,.$

2. Give an example of a column stochastic matrix that is not the identity matrix with

   ${}\det M=1\,$

3. Let ${}d\geq 2$, and suppose that ${}M$ satisfies also the property that there exists a row where all entries are positive. Show

   ${}\vert {\det M}\vert <1\,$

Hand-in-exercises

Exercise (3 marks)

Show that the set of all column stochastic matrices is a closed subset in the space of matrices ${}\operatorname {Mat} _{n}(\mathbb {R} )$.

Exercise (4 marks)

Compute the first four iterations of the column stochastic matrix

${\begin{pmatrix}{\frac {1}{4}}&{\frac {1}{5}}&{\frac {1}{3}}\\{\frac {1}{4}}&{\frac {1}{2}}&{\frac {2}{7}}\\{\frac {1}{2}}&{\frac {3}{10}}&{\frac {8}{21}}\end{pmatrix}}$

for the starting distribution

${\begin{pmatrix}{\frac {1}{3}}\\{\frac {1}{3}}\\{\frac {1}{3}}\end{pmatrix}}.$

Exercise (3 marks)

Compute the eigendistribution of the column stochastic matrix

${\begin{pmatrix}{\frac {1}{4}}&{\frac {1}{5}}&{\frac {1}{3}}\\{\frac {1}{4}}&{\frac {1}{2}}&{\frac {2}{7}}\\{\frac {1}{2}}&{\frac {3}{10}}&{\frac {8}{21}}\end{pmatrix}}.$

Exercise (3 marks)

Show that the product of two column stochastic matrices is again column stochastic. Is the inverse matrix of an invertible column stochastic matrix again column stochastic?

Exercise (8 marks)

A football group of a Europe or World championship consists of four teams, and every team plays versus every other team. A game may end in a tie or with a victory for one of the two teams. We are interested in the discrete structure of a football group, which we describe with the help of a directed graph. A victory of ${}A$ over ${}B$ is described by an arrow from ${}A$ to ${}B$ (and a tie is described by no arrow).

Define a concept of an isomorphism for football groups. Classify the football groups along suitable numeric invariants. How many football groups do exist? When can we deduce from the isomorphism class the order in the table?

<< | Linear algebra (Osnabrück 2024-2025)/Part II | >> PDF-version of this exercise sheet Lecture for this exercise sheet (PDF)