# Question regarding technicalities in the paper Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent

For people on this board I have a probably pretty modest question, but since I'm not a mathematician (just an economist), I'm having trouble. The full pdf can be found here: http://www.pnas.org/content/early/2012/05/16/1206569109.full.pdf+html

The question is regarding the following passage and has to do with linear algebra. They write: "where Adj(M′) is the adjugate matrix (also known as the classical adjoint or, as in high-school algebra, the “matrix of minors”). Eq. 2 implies that every row of Adj(M′) is proportional to v. Choosing the fourth row, we see that the components of v are (up to a sign) the determinants of the 3 × 3 matrices formed from the first three columns of M′, leaving out each one of the four rows in turn. These determinants are unchanged if we add the first column of M′ into the second and third columns. The result of these manipulations is a formula for the dot product of an arbitrary four-vector f with the stationary vector v of the Markov matrix, v · f ≡ D(p; q; f), where D is the 4 × 4 determinant shown explicitly in Fig. 2B. This result follows from expanding the determinant by minors on its fourth column and noting that the 3 × 3 determinants multiplying each fi are just the ones described above."

To understand the full context you will probably have to read the beginning of the passage, which is also very short. Yet my question is specifically regarding the formulated relationship between the stationary vector v of the Markov transition-matrix M and the Adj(M'), which is Adj.(M-I). As they say: Every row of Adj.(M') is proportional to v, which is sort of intuitive looking at Eq. 2, but I simply do not understand how they got that. Also the immediately following conclusion that the elements of v are the 3x3 column determinants of M' if you were to eliminate from the bottom of the fourth column.

Also to point out a petty mistake but v · f ≡ D(p; q; f) can't be correct as the dimensions do not link up correctly. v' · f ≡ D(p; q; f) is correct. But yet again I grasp that this formulation makes sense, but fail to understand how this can be arrived at.

If you can point me in the direction of a book or can flat-out explain this to me, I would be very obliged.

Thanks in advance o_s

-

A very interesting paper!

On every row of $\operatorname{Adj}(\mathbf M')$ being proportional to $\mathbf v$: This isn't fully justified in the paper. In speaking of "the stationary vector $\mathbf v$ of the Markov matrix", they're implicitly using the fact that the matrix has a unique stationary vector. That's not trivial; an irreducible Markov chain has a unique stationary distribution if and only if all its states are positive recurrent. (For that statement and an explanation of the terminology it uses see Wikipedia.) If it does have a unique stationary vector (i.e. a unique left eigenvector with eigenvalue $1$), then all vectors with $\mathbf x^\top M=\mathbf x^\top$, or equivalently $\mathbf x^\top(\mathbf M-\mathbf I)=0$, must be proportional to that vector, and equation [2] says precisely that every row of $\operatorname{Adj}(\mathbf M')$ satisfies $\mathbf x^\top(\mathbf M-\mathbf I)=0$.

On the components of $\mathbf v$ being given by these $3\times3$ determinants: This is a bit imprecise; $\mathbf v$ was introduced as the stationary vector of the Markov matrix, which should be normalized to sum to $1$; equation [2] only says that $\mathbf v$ is proportional to the vector formed from these determinants. (This is because the fourth row of $\operatorname{Adj}(\mathbf M')$ is defined by these determinants, and as discussed above each row of $\operatorname{Adj}(\mathbf M')$ is proportional to $\mathbf v$.) This imprecision is corrected on the next page, where the payoffs are noramlized using $\mathbf v\cdot\mathbf 1$.

On replacing $\mathbf v\cdot\mathbf f$ by $\mathbf v'\cdot\mathbf f$: I'm not sure what you mean by $\mathbf v'$, but if you mean $\mathbf v^\top$, the transpose of $\mathbf v$, note that the dot notation $\mathbf v\cdot\mathbf f$ for the dot product of two column vectors is quite usual; to write it in matrix notation as you seem to have in mind, you should simply write $\mathbf v^\top\mathbf f$ without a dot, since it's unusual to use dots for matrix multiplication. You can see that the dot product is given by this determinant by applying the Laplace expansion to the last column (the one containing $\mathbf f$).

-
Thank you for your detailed answer, but due to my lackluster math education I will need to do some further reading. On the last paragraph: I did not know that this notation usual and i did mean the transpose v. That the Laplace expansion on the fourth row was relevant, I was able to grasp and also that this syncs up with the determinants. –  option_select Aug 18 '12 at 11:50
@option_select: OK, feel free to ask again if you have further questions. –  joriki Aug 18 '12 at 11:53
@option_select: I'm not sure what you mean by "leave the sign permutation of the adjugate formula out". The adjugate of your matrix is $$\pmatrix{ -3 & 6 & -3 \\ 6 & -12 & 6 \\ -3 & 6 & -3 }$$ including the correct signs, so as far as I can tell it's not that one has to leave the signs out but that you left them out at first and then included them to get the correct result. –  joriki Aug 18 '12 at 14:37
You are correct. I looked up the specification in mathematica and it does not return the adjugate but rather just the matrix of minors without the sign. My bad... –  option_select Aug 18 '12 at 14:42
@option_select: You're welcome! –  joriki Aug 18 '12 at 14:57

Here $M$ is a matrix with $1$ as an eigenvalue, $M'=M-I$ and $v$ is a non-zero vector such that $M'v=0$. We have $\operatorname{Adj}(M') M' = 0 = M' \operatorname{Adj}(M')$. If $v_1, \ldots$ are the columns of $M'$ then $M' \operatorname{Adj}(M')$ is the matrix whose columns are $M'v_1, M'v_2,\ldots$, hence all these are zero, i.e. $Mv_i = v_i$ for all $i$.

If the space of 1-eigenvectors of $M$ is one-dimensional, it follows each $v_i$ must be a scalar multiple of $v$. Presumably this eigenspace condition somehow follows from the set-up in this paper. Otherwise the statement is false.

-
Thank you for your answer. Yet I will need some time to understand the statements made. –  option_select Aug 18 '12 at 11:53