What a Transition-Matrix Check Must Establish
A matrix can have plausible-looking entries and still fail to represent the transitions of a Markov model. A negative entry cannot be a probability; a row or column with the wrong total loses or creates probability mass; and a matrix can be valid for one multiplication convention but invalid for another. Even a numerically valid matrix can be misread if its states are listed in a different order from the distribution vector.
We will use a finite set of states \(S_1,\dots,S_n\). A probability distribution is a list of nonnegative numbers, one for each state, whose sum is \(1\). In a column-vector convention, write the distribution as a column \(\mathbf{x}\in\mathbb{R}^n\). In a row-vector convention, write it as a row \(\mathbf{q}\). The entries in either vector follow a specified order of states. A transition matrix records the probability of moving from one state to another in one step.
These are two conventions for recording the same kind of transition information, not interchangeable sum tests. With row-vector multiplication, the entry \(r_{ij}\) is the probability of moving from state \(S_i\) to state \(S_j\), so each row describes the possible destinations from one starting state. With column-vector multiplication, the entry \(p_{ij}\) is the probability of moving from state \(S_j\) to state \(S_i\), so each column describes the destinations from one starting state.
Why the Two Tests Work
The row and column sum conditions are not just convenient bookkeeping. They are exactly the conditions that make the corresponding multiplication carry every probability distribution to another probability distribution.
Proof. First consider the row-vector convention. If \(\mathbf{R}\) is row-stochastic and \(\mathbf{q}\) is a row probability distribution, then the \(j\)th entry of \(\mathbf{q}\mathbf{R}\) is \(\sum_{i=1}^n q_i r_{ij}\), which is nonnegative because every \(q_i\) and \(r_{ij}\) is nonnegative. Its entries sum to \[ \sum_{j=1}^n\sum_{i=1}^n q_i r_{ij} =\sum_{i=1}^n q_i\left(\sum_{j=1}^n r_{ij}\right) =\sum_{i=1}^n q_i=1. \] So the output is a probability distribution. Conversely, suppose multiplication by \(\mathbf{R}\) maps every row probability distribution to a probability distribution. For each \(i\), let \(\mathbf{e}_i^{\top}\) be the row vector with \(1\) in position \(i\) and \(0\) elsewhere. It is a probability distribution, and \(\mathbf{e}_i^{\top}\mathbf{R}\) is row \(i\) of \(\mathbf{R}\). Since this output is a probability distribution, row \(i\) has nonnegative entries summing to \(1\). This holds for every row, so \(\mathbf{R}\) is row-stochastic.
For the column-vector convention, if \(\mathbf{P}\) is column-stochastic and \(\mathbf{x}\) is a column probability distribution, each entry of \(\mathbf{P}\mathbf{x}\) is a sum of nonnegative terms and is therefore nonnegative. The sum of its entries is \[ \sum_{i=1}^n\sum_{j=1}^n p_{ij}x_j =\sum_{j=1}^n x_j\left(\sum_{i=1}^n p_{ij}\right) =\sum_{j=1}^n x_j=1. \] Conversely, let \(\mathbf{e}_j\) be the column vector with \(1\) in position \(j\) and \(0\) elsewhere. It is a probability distribution, and \(\mathbf{P}\mathbf{e}_j\) is column \(j\) of \(\mathbf{P}\). If every input distribution produces a distribution, this column must be nonnegative and sum to \(1\). This holds for every column, so \(\mathbf{P}\) is column-stochastic. \(\square\)
This result gives a direct diagnostic: test the matrix using the multiplication convention intended by the model. The zero and one entries of \(\mathbf{e}_i\) or \(\mathbf{e}_i^{\top}\) isolate one column or row, so the test also explains why each starting state must have a complete probability distribution over its possible next states.
Worked Example: Matching a Matrix to Its Convention
Worked Example: A Valid Row Matrix and Its Column Version
Suppose the states are \(S_1,S_2\), in that order, and the proposed row-convention matrix is
Check each row: \(\frac12+\frac12=1\) and \(\frac14+\frac34=1\). Every entry is nonnegative, so \(\mathbf{R}\) is row-stochastic. Its column sums are \(\frac12+\frac14=\frac34\) and \(\frac12+\frac34=\frac54\); it is not column-stochastic.
For a row distribution \(\mathbf{q}=(1,0)\), meaning all probability is initially on \(S_1\), multiply on the right:
The output entries are nonnegative and sum to \(1\). The column-vector version of this same transition model is the transpose:
The columns of \(\mathbf{P}\) sum to \(1\), since \(\frac12+\frac12=1\) and \(\frac14+\frac34=1\). Its row sums are \(\frac34\) and \(\frac54\), so it is not row-stochastic. With the initial column distribution \(\mathbf{x}=(1,0)^{\top}\), multiplication on the left gives
Check: the output probabilities sum to \(\frac12+\frac12=1\), and both are nonnegative. The matrix \(\mathbf{R}\) is valid with row-vector multiplication, while its transpose \(\mathbf{P}\) is valid with column-vector multiplication. Neither matrix is valid in both conventions: a matrix can use both conventions only if it is doubly stochastic.
Separate Probability Errors from Sum Errors
Two checks are needed because passing one does not guarantee passing the other. Nonnegative entries with a row sum below \(1\) omit probability mass. Row sums of \(1\) with a negative entry still do not describe probabilities. Apply the appropriate sum test to the chosen convention, and inspect the entries independently.
Worked Example: A Negative Entry Despite Correct Row Sums
Consider the proposed row-stochastic matrix
Both row sums equal \(1\): \(\frac54-\frac14=1\) and \(\frac13+\frac23=1\). But the entry \(-\frac14\) is negative, so \(\mathbf{A}\) is not a valid transition matrix. For the initial row distribution \((1,0)\), the output is the first row:
Check: the output sums to \(\frac54-\frac14=1\), but it contains a negative “probability.” A correct total alone does not make the output a probability distribution. The theorem’s nonnegativity requirement is essential.
Worked Example: Nonnegative Entries with a Missing Row Total
Now consider
All entries are nonnegative. The first row sums to \(\frac34+\frac14=1\), but the second sums to \(\frac13+\frac12=\frac56\). Thus \(\mathbf{B}\) is not row-stochastic. With the row distribution \(\mathbf{q}=(\frac13,\frac23)\), the output is
Check: the output entries are nonnegative, but their sum is \(\frac{17}{36}+\frac{15}{36}=\frac{32}{36}=\frac89\), not \(1\). The missing probability can be traced to the starting mass \(\frac23\) on the second state, whose row sums to only \(\frac56\). Its contribution is reduced by the factor \(\frac56\), so the total becomes \(\frac13\cdot1+\frac23\cdot\frac56=\frac13+\frac59=\frac89\).
State Ordering Is Part of the Model
A vector’s coordinates and a transition matrix’s rows and columns refer to particular named states. A matrix with the correct numerical entries can appear to give a wrong answer when its rows and columns use one order but the distribution uses another. Whenever the state order changes, reorder both matrix indices and the distribution coordinates consistently.
Proof. Write the new state order as \(S_{\pi(1)},\dots,S_{\pi(n)}\), where \(\pi\) is a rearrangement of the original indices. The new matrix has entry \(r_{\pi(i),\pi(j)}\) in row \(i\), column \(j\), because both the starting-state index and destination-state index have been renamed. The new distribution has entry \(q_{\pi(i)}\) in position \(i\). Its \(j\)th output coordinate is therefore \(\sum_{i=1}^n q_{\pi(i)}r_{\pi(i),\pi(j)}\), which is exactly the old output coordinate for state \(S_{\pi(j)}\). Thus the computed probabilities are the same, only listed in the new order. \(\square\)
Worked Example: Reordering Three States
Let the original state order be \(A,B,C\), and let the row-stochastic matrix be
Thus \(A\) moves to \(B\), \(B\) moves to \(A\) or \(C\) with probability \(\frac12\) each, and \(C\) remains at \(C\). The rows sum to \(1\): \(0+1+0=1\), \(\frac12+0+\frac12=1\), and \(0+0+1=1\). Now use the new order \(C,A,B\). Taking the old rows and columns in the order \(3,1,2\) gives
Its rows still sum to \(1\): \(1+0+0=1\), \(0+0+1=1\), and \(\frac12+\frac12+0=1\). A distribution concentrated at \(A\) is now \((0,1,0)\), not \((1,0,0)\). Multiplying in the reordered system gives
Check: in the new order, \((0,0,1)\) assigns all probability to \(B\), as required by the transition \(A\to B\). If one incorrectly uses \((1,0,0)\) as the initial vector, the calculation instead starts at \(C\): \((1,0,0)\mathbf{R}_{\mathrm{new}}=(1,0,0)\). The arithmetic is valid, but the input was mislabeled.
A Practical Diagnostic Routine
When checking a proposed model, keep the following stages separate. They catch different mistakes, and the order prevents a correct-looking output from hiding an invalid input.
Record the exact state labels and their order for both matrix indices and distribution coordinates. Do not infer the order from a matrix alone.
For \(\mathbf{q}_{\text{next}}=\mathbf{q}\mathbf{R}\), check rows. For \(\mathbf{x}_{\text{next}}=\mathbf{P}\mathbf{x}\), check columns.
All entries must be nonnegative, and each row or column selected by the convention must sum to \(1\).
A distribution with one coordinate equal to \(1\) isolates one row or column. Confirm that it gives the transitions intended for that starting state.
This last check is particularly useful for detecting a transpose error. If a row-stochastic matrix is accidentally multiplied as \(\mathbf{R}\mathbf{x}\) with a column distribution, the column sums, rather than the row sums, control the total. In the first worked example, the mistaken computation with \(\mathbf{R}\) and \(\mathbf{x}=(1,0)^{\top}\) gives
The entries sum to \(\frac34\), so the result is not a probability distribution. The correction is not to renormalize this output without explanation: use the row vector \((1,0)\) on the right of \(\mathbf{R}\), or use \(\mathbf{P}=\mathbf{R}^{\top}\) on the left of a column distribution.
Common Pitfall: A Matrix Is Not Valid in Both Conventions by Default
A frequent error is to say that a row-stochastic matrix and its transpose are both “valid either way.” The first worked example shows why that statement is false. Its row-stochastic matrix has column sums \(\frac34\) and \(\frac54\), while its transpose is column-stochastic but has row sums \(\frac34\) and \(\frac54\). Each matrix is valid with its matching vector orientation; neither is valid with the other orientation.
Only a doubly stochastic matrix passes both sum tests, and it must still have nonnegative entries. For instance, \(\begin{bmatrix}0&1\\1&0\end{bmatrix}\) has nonnegative entries, and every row and column sums to \(1\). But this special case should not be assumed of an arbitrary transition matrix. A reliable diagnosis therefore names the vector orientation, checks the corresponding sums, verifies nonnegativity, and matches every coordinate to the stated state order.
Check Your Understanding
For each proposed model, state the convention you would use and justify the checks needed.
- Is \(\begin{bmatrix}\frac12&\frac12\\0&1\end{bmatrix}\) row-stochastic, column-stochastic, both, or neither?
- For a column-stochastic matrix, explain why multiplying a column probability distribution on the right is not the convention tested by the column-sum condition.
- A row-stochastic matrix has a negative entry. Which condition fails, and how can a concentrated starting distribution expose the problem?
- If state order changes from \(A,B,C\) to \(B,C,A\), what must change in the matrix and in the distribution vector?
- Give a reason why output entries summing to \(1\) do not by themselves prove that a proposed transition matrix is valid.
