Here’s a simple but surprising theorem from digital signal processing: linear, time-invariant (LTI) operators commute. The order in which you apply LTI operators does not matter.

**Linear** in DSP means just you’d expect from seeing linear defined anywhere else: An operator *L* is linear if given any two signals *x*_{1} and *x*_{2}, and any two constants α and β,

*L*(α*x*_{1} + β*x*_{2}) = α*L*(*x*_{1}) + β*L*(*x*_{2}).

**Time-invariant** means that an operation does not depend on how we label our samples. More precisely, an operation *T* is time-invariant if it commutes with shifts:

*T*( *x*[*n* − *h*] ) = *T*(*x*)[*n* − *h*]

for all *n* and *h*.

Linear operators do not commute. Time-invariant operators do not commute. But operators that are both linear **and** time-invariant **do** commute*.*

Linear operators are essentially multiplication by a matrix, and matrix multiplication isn’t commutative: the order in which you multiply matrices matters.

Here’s an example to show that time-invariant operators do not commute. Suppose *T*_{1} operates on a sequence by squaring every element and *T*_{2} adds 1 to every element. Applying *T*_{1} and then *T*_{2} sends *x* to *x*² + 1. But applying *T*_{2} and then *T*_{1} sends *x* to (*x* + 1)². These are not the same if any element of *x* is non-zero.

So linear operators don’t commute, and time-invariant operators don’t commute. Why do operators that are both linear and time invariant commute? There’s some sort of synergy going on, with the combination of properties having a new property that neither has separately.

In a nutshell, a linear time-invariant operator is given by **convolution** with some sequence. Convolution commutes, so linear time-invariant operators commute.

Suppose the effect of applying *L*_{1} to a sequence *x* is to take the convolution of *x* with a sequence *h*_{1}:

*L*_{1} *x* = *x* * *h*_{1}

where * means convolution.

Suppose also the effect of applying *L*_{2} to a sequence is to take the convolution with *h*_{2}.

*L*_{2} *x* = *x* * *h*_{2}.

Now

*L*_{1} (*L*_{2} *x*) = *x* * *h*_{2} * *h*_{1} = *x* * *h*_{1} * *h*_{2} = *L*_{2} (*L*_{1} *x*)

and so *L*_{1} and *L*_{2} commute.

The post hasn’t gone in to full detail. I didn’t show that LTI systems are given by convolution, and I didn’t show that convolution is commutative. (Or associative, which I implicitly assumed.) But I have reduced the problem to verifying three simpler claims.

Nice observation!

Working in signal processing, this commutativity is so natural that we rarely think about. I hadn’t thought of it as anything special until today.

I had not seen this DSP theorem before. It is related to the linear algebra theorem that circulant matrices commute and the functional analysis theorem that infinite Toeplitz matrices commute. Wikipedia says that (finite) Toeplitz matrices “commute asymptotically” (i.e., for the dimensions tending to infinity).