LTI operators commute

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₁ and x₂, and any two constants α and β,

L(αx₁ + βx₂) = αL(x₁) + βL(x₂).

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₁ operates on a sequence by squaring every element and T₂ adds 1 to every element. Applying T₁ and then T₂ sends x to x² + 1. But applying T₂ and then T₁ 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₁ to a sequence x is to take the convolution of x with a sequence h₁:

L₁ x = x * h₁

where * means convolution.

Suppose also the effect of applying L₂ to a sequence is to take the convolution with h₂.

L₂ x = x * h₂.

Now

L₁ (L₂ x) = x * h₂ * h₁ = x * h₁ * h₂ = L₂ (L₁ x)

and so L₁ and L₂ 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.