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 x1 and x2, and any two constants α and β,
L(αx1 + βx2) = αL(x1) + βL(x2).
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 T1 operates on a sequence by squaring every element and T2 adds 1 to every element. Applying T1 and then T2 sends x to x² + 1. But applying T2 and then T1 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 L1 to a sequence x is to take the convolution of x with a sequence h1:
L1 x = x * h1
where * means convolution.
Suppose also the effect of applying L2 to a sequence is to take the convolution with h2.
L2 x = x * h2.
L1 (L2 x) = x * h2 * h1 = x * h1 * h2 = L2 (L1 x)
and so L1 and L2 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.
2 thoughts on “LTI operators commute”
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).