Why Matrix Multiplication Order Matters

Why the Order of Updates Matters

In a multi-state model, a transition matrix describes how probability is redistributed among states. When events occur at different times, each event updates the probabilities produced by the events before it. Matrix multiplication combines those updates, but its order is consequential: in general, multiplying matrix \(M_1\) by \(M_2\) does not give the same result as multiplying \(M_2\) by \(M_1\).

This is not merely an algebraic detail. The intermediate state after the first event determines which transitions are possible at the second. Reversing the event-time order can therefore change the probabilities of being in each state at the end of the interval, even if the same two transition updates are used.

Definition: Use rows for origin states and columns for destination states. If \(M(u)\) is the transition update at event time \(u\), then the transition matrix over successive event times \(u_1<u_2<\cdots<u_m\) is the ordered product \(M(u_1)M(u_2)\cdots M(u_m)\). Each update is multiplied on the right of the transition matrix accumulated so far.

This convention agrees with row-vector state probabilities: if \(\boldsymbol{\pi}\) is a row vector giving the starting-state distribution, then the ending distribution is \(\boldsymbol{\pi}M(u_1)\cdots M(u_m)\). For a single starting state, \(\boldsymbol{\pi}\) has probability 1 in that state and 0 in every other state. The diagonal entries of an update include the probability of remaining in the same state at that update.

The calculations below assume a finite state space, valid transition updates with nonnegative entries and rows summing to 1, and event times in the stated chronological order. Updates represent the transitions over their respective event times; no other update is applied between them. The product then gives the transition probabilities across the combined interval. In applications based on estimated transition intensities, the event-time updates and their recursion provide the corresponding discrete product-integral calculation.

A Noncommuting Pair of Updates

Consider three states, labeled 0, 1, and 2, with state 2 absorbing. Suppose that at an earlier event, update \(A\) permits a transition from state 0 to state 1 with probability 0.4, and from state 1 to state 2 with probability 0.2. At a later event, update \(B\) permits a transition from state 0 to state 2 with probability 0.3, and from state 1 to state 2 with probability 0.5. These are hypothetical updates.

Worked Example: Multiplying Two Updates in Event-Time Order

Write the two row-stochastic updates and calculate the transition matrix when \(A\) occurs before \(B\). Then compare it with the product obtained by reversing their order.

The updates, with rows and columns ordered as states 0, 1, 2, are

A= \begin{pmatrix} 0.6&0.4&0\\ 0&0.8&0.2\\ 0&0&1 \end{pmatrix}, \qquad B= \begin{pmatrix} 0.7&0&0.3\\ 0&0.5&0.5\\ 0&0&1 \end{pmatrix}.

Each row sums to 1, and no entry is negative, so both matrices are valid transition updates. Since \(A\) occurs first, the chronological product is \(AB\). For example, its first row is computed by multiplying the first row of \(A\) by each column of \(B\):

\begin{aligned} (AB)_{00}&=0.6(0.7)+0.4(0)+0(0)=0.42,\\ (AB)_{01}&=0.6(0)+0.4(0.5)+0(0)=0.20,\\ (AB)_{02}&=0.6(0.3)+0.4(0.5)+0(1)=0.38. \end{aligned}

The second row is \((0,0.8,0.2)B=(0,0.4,0.6)\), and the third row remains \((0,0,1)\). Thus

AB= \begin{pmatrix} 0.42&0.20&0.38\\ 0&0.40&0.60\\ 0&0&1 \end{pmatrix}.

Reversing the order gives a different result. Direct multiplication gives

BA= \begin{pmatrix} 0.42&0.28&0.30\\ 0&0.40&0.60\\ 0&0&1 \end{pmatrix}.

For instance, the first row of \(BA\) is \((0.7,0,0.3)A=(0.42,0.28,0.30)\). Both products have nonnegative entries and rows summing to 1, but they are not equal. Starting in state 0, the probability of ending in state 1 is 0.20 under the chronological order \(AB\), versus 0.28 under the reversed order \(BA\). The probability of ending in state 2 is 0.38 versus 0.30, respectively. These are differences in transition probabilities, not rounding discrepancies.

Why the Products Differ

The matrix multiplication formula gives a direct justification. For two updates \(M_1\) and \(M_2\), the entry in row \(i\), column \(j\) of \(M_1M_2\) is a sum over possible intermediate states \(k\). Each term \( (M_1)_{ik}(M_2)_{kj}\) is the probability of moving from \(i\) to \(k\) at the first update and then from \(k\) to \(j\) at the second. Reversing the factors instead sums the probabilities of paths that first use \(M_2\), then \(M_1\).

In general, these are different collections of path probabilities. Algebraically, the difference in a particular entry is

(M_1M_2-M_2M_1)_{ij} = \sum_k \left[(M_1)_{ik}(M_2)_{kj}-(M_2)_{ik}(M_1)_{kj}\right].

The two products agree exactly when the matrices commute, meaning \(M_1M_2=M_2M_1\). They can differ only in entries where the two orders produce different total probabilities of reaching a destination through intermediate states. This entrywise argument establishes both why multiplication order matters and the condition under which it does not.

Worked Example: Event Order Opens or Closes a Path

Suppose a first event can move a person from state 0 to state 1 with probability 0.5, while a second event can move a person from state 1 to absorbing state 2 with probability 0.6. State 0 is unaffected by the second event, and state 1 is unaffected by the first event except for remaining there. The updates are

C= \begin{pmatrix} 0.5&0.5&0\\ 0&1&0\\ 0&0&1 \end{pmatrix}, \qquad D= \begin{pmatrix} 1&0&0\\ 0&0.4&0.6\\ 0&0&1 \end{pmatrix}.

If \(C\) occurs before \(D\), then the product is

CD= \begin{pmatrix} 0.5&0.5&0\\ 0&0.4&0.6\\ 0&0&1 \end{pmatrix} \begin{pmatrix}\text{(product calculation)}\end{pmatrix} = \begin{pmatrix} 0.5&0.2&0.3\\ 0&0.4&0.6\\ 0&0&1 \end{pmatrix}.

The first row can also be read by paths: the probability of reaching state 2 is \(0.5(0.6)=0.30\), because the first event must move the person to state 1 before the second event can move them to state 2. The probability of ending in state 1 is \(0.5(0.4)=0.20\); the probability of remaining in state 0 is 0.50.

If \(D\) occurs first, someone starting in state 0 cannot use its state-1-to-state-2 transition, because they are still in state 0. The later \(C\) update can move them to state 1, but there is no subsequent \(D\) update. Direct multiplication confirms this:

DC= \begin{pmatrix} 1&0&0\\ 0&0.4&0.6\\ 0&0&1 \end{pmatrix} \begin{pmatrix} 0.5&0.5&0\\ 0&1&0\\ 0&0&1 \end{pmatrix} = \begin{pmatrix} 0.5&0.5&0\\ 0&0.4&0.6\\ 0&0&1 \end{pmatrix}.

From state 0, the probability of reaching state 2 is therefore 0.30 under \(CD\), but 0 under \(DC\). The matrix entries and path explanation agree. Each product is a valid transition matrix, but only \(CD\) corresponds to the specified chronology in which \(C\) precedes \(D\).

When Reversing the Order Makes No Difference

The fact that order can matter does not mean it must always matter. For example, two updates that affect the same one-way transition can commute. In the next hypothetical example, state 1 is absorbing, and both event updates allow only a transition from state 0 to state 1.

Worked Example: A Pair of Updates That Commute

Suppose the first update moves probability 0.2 from state 0 to state 1, and the second moves probability 0.5 from state 0 to state 1. The updates are

E= \begin{pmatrix} 0.8&0.2\\ 0&1 \end{pmatrix}, \qquad F= \begin{pmatrix} 0.5&0.5\\ 0&1 \end{pmatrix}.

Multiplying in the order \(EF\) gives

EF= \begin{pmatrix} 0.8(0.5)&0.8(0.5)+0.2(1)\\ 0&1 \end{pmatrix} = \begin{pmatrix} 0.4&0.6\\ 0&1 \end{pmatrix}.

In the reversed order,

FE= \begin{pmatrix} 0.5(0.8)&0.5(0.2)+0.5(1)\\ 0&1 \end{pmatrix} = \begin{pmatrix} 0.4&0.6\\ 0&1 \end{pmatrix}.

Here \(EF=FE\), so reversing the two updates leaves the transition probabilities unchanged. Both updates have the same absorbing destination, and neither creates a route from state 1 back to state 0. The product retains the probability of remaining in state 0, \(0.8(0.5)=0.4\), regardless of the order. This is a special property of this pair of matrices, not a general rule for transition updates.

Calculation Checks and Common Pitfalls

A reliable calculation starts by writing down the time ordering and the matrix convention. With row vectors and row-stochastic matrices, the chronological update is on the right. If column vectors are used instead, the corresponding convention changes; mixing the two conventions can produce an incorrect product even when each matrix is valid.

After multiplication, check that every entry is nonnegative and every row sums to 1. These checks can detect arithmetic or transcription errors, but they cannot detect a product that uses the wrong event-time order: both \(AB\) and \(BA\) in the first example satisfy these checks. Compare the stated chronology to the factors in the product, and, when order sensitivity is in question, calculate both products or inspect whether the matrices commute.

Common mistake: treating multiplication as commutative. The reasoning “the same two updates occur, so their order does not matter” is false in general. The correction is to preserve chronological order and compare \(M_1M_2\) with \(M_2M_1\) if the effect of reversing the order is being assessed.
Common mistake: interpreting a valid row sum as evidence of correct chronology. Row sums of 1 verify probability conservation, not the event sequence. The correction is to check both stochastic validity and the order of the factors.
Common mistake: adding transition changes instead of multiplying updates. A sum of increments does not generally account for paths that pass through an intermediate state at an earlier event and then transition again. The correction for discrete event updates is to apply the ordered matrix product.

For a small state space, direct multiplication is usually the clearest method. A path-based calculation can provide an independent check by summing probabilities over all relevant intermediate states. These approaches answer the same question in different forms: matrix multiplication organizes all paths at once, while path enumeration makes the intermediate-state contributions explicit. Neither justifies changing the time order.

The result is limited to the specified updates and chronology. It does not say which ordering is appropriate when event times are unknown or tied; those are separate modeling and data questions. Nor does an order-sensitive difference establish a causal effect of changing event times. It states that, under the updates shown, the resulting transition probabilities depend on the order in which the updates are applied.

Key takeaway: Under the row-vector convention, apply each transition update on the right in chronological order. The products can differ when the updates do not commute, because the first update changes the intermediate-state distribution on which the second update acts.

Check Your Understanding

Use the row-origin, column-destination convention throughout. The solutions are included below the questions.

For the first worked example, what is the chronological product if \(B\) occurs before \(A\)? What is the probability of ending in state 2 from state 0?
In the second worked example, explain why the probability of reaching state 2 from state 0 is zero when \(D\) precedes \(C\).
What two checks can establish that a calculated product is a valid transition matrix? Why do they not establish that its factors are in the correct order?
For the commuting example, what is the probability of ending in state 1 from state 0 after both updates?

Solutions. (1) The product is \(BA\); its first row is \((0.42,0.28,0.30)\), so the probability of ending in state 2 is 0.30. (2) The first update \(D\) acts while the person is in state 0, where it leaves them; the later \(C\) update can move them to state 1 but cannot then move them to state 2. (3) Check that entries are nonnegative and that each row sums to 1. Both orders can pass these checks, so chronology must be verified separately. (4) The first row of either product \(EF\) or \(FE\) is \((0.4,0.6)\), so the probability of ending in state 1 is 0.60.