any deep thinking on why linear systems are commutative?

Dear all,

Could you please help me understand better by providing some deep thoughts 
on why linear systems are commutative?

If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))

y1 and y2 are the same.

After seeing some examples of non-linear system and linear systems. I got 
convinced that for non-linear system this property does not hold.

But any deeper thinking? Proof?

Thanks a lot! 

"kiki" <lunaliu3@yahoo.com> wrote in message
news:cljh80$btq$1@news.Stanford.EDU...
> Dear all,
>
> Could you please help me understand better by providing some deep thoughts
> on why linear systems are commutative?
>
> If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))
>
> y1 and y2 are the same.
>
> After seeing some examples of non-linear system and linear systems. I got
> convinced that for non-linear system this property does not hold.
>
> But any deeper thinking? Proof?
>
> Thanks a lot!
>

What exactly do you mean by a "linear system"?  If you can write down a
mathematical description of it, I suspect you'd have answered your own
question.

BUT ... There are systems that look like they're linear in which
commutatively doesn't hold.  Quantum Mechanics springs to mind.  Does that
mean it isn't linear or that all linear systems aren't commutative?

    Norm

On Mon, 25 Oct 2004 11:38:55 -0700, "kiki" <lunaliu3@yahoo.com> wrote:

>Dear all,
>
>Could you please help me understand better by providing some deep thoughts 
>on why linear systems are commutative?
>
>If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))
>
>y1 and y2 are the same.
>
>After seeing some examples of non-linear system and linear systems. I got 
>convinced that for non-linear system this property does not hold.
>
>But any deeper thinking? Proof?

This is not true, so a proof is going to need to be _very_ deep.
(Or if it's true I'm totally misunderstanding what you mean by
"linear system"...)

>Thanks a lot! 
>


************************

David C. Ullrich

kiki wrote:
> Dear all,
> 
> Could you please help me understand better by providing some deep thoughts 
> on why linear systems are commutative?
> 
> If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))
> 
> y1 and y2 are the same.
> 
> After seeing some examples of non-linear system and linear systems. I got 
> convinced that for non-linear system this property does not hold.
> 
> But any deeper thinking? Proof?
> 
> Thanks a lot! 
> 

To answer the subject line: Composition of linear (time invariant)
systems is convolution of their impulse responses. Now you can
prove that, including the commuting part in passing, various ways
so it is true for ALL LTI systems.

But to prove it is not the case for nonlinear you only need ONE
exception which you seem to have already found.

> 

"David C. Ullrich" <ullrich@math.okstate.edu> wrote in message
news:eljqn010mtqq2psn2cfdln9l53plhrd8er@4ax.com...
> On Mon, 25 Oct 2004 11:38:55 -0700, "kiki" <lunaliu3@yahoo.com> wrote:
>
> >Dear all,
> >
> >Could you please help me understand better by providing some deep thoughts
> >on why linear systems are commutative?
> >
> >If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))
> >
> >y1 and y2 are the same.
> >
> >After seeing some examples of non-linear system and linear systems. I got
> >convinced that for non-linear system this property does not hold.
> >
> >But any deeper thinking? Proof?
>
> This is not true, so a proof is going to need to be _very_ deep.
> (Or if it's true I'm totally misunderstanding what you mean by
> "linear system"...)

A couple of thoughts:  I think you also need to add "time-invariant" to your
requirement for being commutative.  Maybe you were assuming a static system, but
it's good to be explicit about that.  Sometimes shift-invariant is used instead
in a sampled data/digital system.

I don't know about the general case, but for something simple such as T1 and T2
being different (linear) filters, it certainly holds.  A really simple example
if making a band-pass filter out of a low-pass and high-pass filter.  It doesn't
matter if you run the signal through the LP first and then run the result
through the HP or vice versa.  (I'm talking the world pure mathematics here, so
things such as round-off error/quantization noise are ignored.)  Are there
examples where two linear time-invariant systems are not commutative?

In the DSP world, the general definition for a linear system is where the
principle of super-position holds.  In layman's terms, put in twice the input
and you get twice the output (T(g*a) = g*T(a).  Or put in a + b and the answer
is the same as if you put in a, then b, and added the results (T(a+b) = T(a) +
T(b)).  I noticed this is posted to sci.math as well, and perhaps a different
definition is used there?

kiki wrote:

> Dear all,
> 
> Could you please help me understand better by providing some deep thoughts 
> on why linear systems are commutative?
> 
> If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))
> 
> y1 and y2 are the same.
> 
> After seeing some examples of non-linear system and linear systems. I got 
> convinced that for non-linear system this property does not hold.
> 
> But any deeper thinking? Proof?
> 
> Thanks a lot! 
> 
> 
Kiki, David, Norm:

I think that Kiki means a linear system in the signal processing sense, 
i.e. the definition in Oppenheim and Willsky, "Signals and Systems", 
1983.  It states that a system is "any process that results in the 
transformation of signals."  "Thus, a system has an input signal and an 
output signal which is related to the input through the system 
transformation".

So a system is one where for two scalar signals x(t) and y(t), and a 
system h, h will transform x(t) into y(t) such that y(t) = h(x(t), t) 
depends only on the value of x over all time, on the value of t and on 
the properties of h.

Take two multipliers a_1 and a_2, and two input signals x_1 and x_2. 
Generate an input signal equal to

x(t) = a_1*x_1(t) + a_2*x_2(t)

A system h is linear in this sense if and only if

y(t) = h(x(t), t) = a_1*h(x_1(t), t) + a_2*h(x_2(t), t).

Linear time invariant systems (i.e. a system h where y(t-a) = h(x(t-a), 
t) iff y(t) = h(x(t), t)) are commutative -- one finds that any linear 
time invariant system can be described as a convolution operation, then 
one finds that convolution operations are commutative, and viola!  one 
has a proof.  Oppenheim has, I believe, a proof.  I believe that 
time-invariance is not necessary, but I don't know and I'm too lazy to 
look it up or prove it at the moment.

Nonlinear systems are, in general, not commutative.  For instance the 
(nonlinear) system h_1(x(t), t) = x(t)^2 doesn't commute with the 
(linear) system h_2(x(t), t) = 42*x(t) -- applying h_1 first yields y = 
42*x^2, where applying it second yields y = 1764*x^2, so they clearly 
aren't equal.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

kiki wrote:

>Could you please help me understand better by providing some deep thoughts 
>on why linear systems are commutative?
>
>If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))
>
>y1 and y2 are the same.
>
>After seeing some examples of non-linear system and linear systems. I got 
>convinced that for non-linear system this property does not hold.
>
>But any deeper thinking? Proof?
>

I thought this would cause confusion amongst the mathematicians.  The OP 
is referring to systems theory as covered in electrical engineering, I 
believe.  If I recall correctly from over twenty years ago when I had to 
work with these things,   let  I  be either the nonnegative reals or the 
natural numbers.  A linear system is a linear map from  R^I  to  R^I.  
As another poster has pointed out, you may need time-invariance for 
commutativity.  That is,  letting L_t  be the map such that  [L_t (x)] 
(s) = x(t+s)   for all  s in I,  T  and  L_t  commute for all  
nonnegative  t.  (I may be messing this definition up a little.)

Signal processing always struck me as applied functional analysis.


-- 
Stephen J. Herschkorn                        herschko@rutcor.rutgers.edu

"Stephen J. Herschkorn" <herschko@rutcor.rutgers.edu> wrote in message
news:fHcfd.14194$bz4.1975817@news4.srv.hcvlny.cv.net...
>
> Signal processing always struck me as applied functional analysis.

Functional analysis always struck me as abstract signal processing.  :-)

Tim Wescott wrote:

> has a proof.  Oppenheim has, I believe, a proof.  I believe that 
> time-invariance is not necessary, but I don't know and I'm too lazy to 
> look it up or prove it at the moment.

News flash (well, news to me at least):

Time invariance _is_ necessary.  If you have a signal x(t) = 1, h_1(x, 
t) = x*sin(w*t), h_2(x, t) = x convolve e^(-w*t) (i.e. a low-pass 
filter), then cascading with h_1 first gives you a delayed, attenuated 
sine wave, where h_2 first gives you just the sine wave.

The commutative property also won't hold for MIMO systems, but I'll 
leave counter examples as an exercise for the reader.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

"kiki" <lunaliu3@yahoo.com> wrote in message news:<cljh80$btq$1@news.Stanford.EDU>...
> Dear all,
> 
> Could you please help me understand better by providing some deep thoughts 
> on why linear systems are commutative?
> 
> If T1 and T2 are linear systems, then y1=T2(T1(x)) and y2=T1(T2(x))
> 
> y1 and y2 are the same.
> 
> After seeing some examples of non-linear system and linear systems. I got 
> convinced that for non-linear system this property does not hold.
> 
> But any deeper thinking? Proof?
> 
> Thanks a lot!

Given:
T1(x) = m1*x + b1
T2(x) = m2*x + b2

Then:
T2(T1(x)) = m2 * (m1*x+b1) + b2 = m2*m1*x + m2*b1 + b2
T1(T2(x)) = m1 * (m2*x+b2) + b1 = m1*m2*x + m1*b2 + b1

Thus T2(T1(x)) not equal T1(T2(x)) for linear systems