Question about Linear systems

On Sat, 06 Oct 2007 14:09:13 +0000, Anja wrote:

>> A definitiion and test for a linear system can be found here:
>>
>> http://en.wikipedia.org/wiki/Linear_system
>>
>> A system that multiplies two inputs fails the test.
> 
> I looked at this page but am still unable to understand how and where
> it fails the test. Mathematics is not my strong point (though I am
> working on it every day!). Is it possible that you can explain a bit
> as to what constraints are violated?
> 

This is a newsgroup, please retain quoted text for context.

Your question was about a system that multiplies two signals together, and
why that's not a linear system.  They're actually throwing a bit of a
curve ball at you, in that to make the problem fit the formal definition
of linearity you have to accept an vector input signal (i.e. a 2-piece
signal, in this case).

At any rate, you've got an input signal [x, w], and a system that gives
you an output signal y = x * w.

For linearity to hold, your system must obey superposition: for any two
signals the sum of the system's response to each signal must equal the
system's response to the sum of the signals.  This is saying that

(x1 + x2) * (w1 + w2) = (x1 * w1) + (x2 * w2)

Now, I know you say your math isn't strong, but you ought to be able to
multiply out the left hand side of this and see that it doesn't equal the
right.

One of the nice things about the superposition principal of linear systems
is that as soon as you find _any_ pair of signals that violates the
principal you've shown that the system is nonlinear; you don't have to
keep trying.

-- 
Tim Wescott
Control systems and communications consulting
http://www.wescottdesign.com

Need to learn how to apply control theory in your embedded system?
"Applied Control Theory for Embedded Systems" by Tim Wescott
Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html

Anja <anja.ende@googlemail.com> writes:

> > A definitiion and test for a linear system can be found here:
> >
> > http://en.wikipedia.org/wiki/Linear_system
> >
> > A system that multiplies two inputs fails the test.
> 
> I looked at this page but am still unable to understand how and where
> it fails the test. Mathematics is not my strong point (though I am
> working on it every day!). Is it possible that you can explain a bit
> as to what constraints are violated?

Have you tried plugging in the multiplication of two sinusoids into
the equations on the Wikipedia page to see what happens?

Start with:  H{ BLAH } = sin(w0*t)*BLAH

and then plug in x1 = sin(w1*t) and x2 = sin(w2*t) and see what
happens.

Ciao,

Peter K.


-- 
"And he sees the vision splendid 
of the sunlit plains extended
And at night the wondrous glory of the everlasting stars."

 

On Oct 6, 11:18 am, Andor <andor.bari...@gmail.com> wrote:
> A "system" (*) H is linear iff
>
> H(a x1  +  b x2)  =  a H(x1)  +  b H(x2)
>
> for all numbers a and b and all signals x1 and x2 (just showing the
> above condition to be true for a specific pair of signals will not
> do).

i.e. *you* don't get to choose a or b or x1 or x2, the devil gets to
choose those numbers or signals and to establish linearity, you have
to show that the above superposition equation is true nonetheless.

BTW, the scaling properties,

   H(a x1)  =  a H(x1)

need not be axiomatically part of the criterion for defining
linearity.  the superposition property

   H(x1  +  x2)  =  H(x1)  +  H(x2)

is sufficient and you can derive the scaling property (for all
rational "a") directly from the superposition property.  for
irrational "a", you have to hand-wave a sorta continuity assumption
(or get utterly anal about measure theory that you get in Real
Analysis or Advanced Calculus or whatever they're calling it) that is
perfectly reasonable for physical systems.

r b-j

"Anja" <anja.ende@googlemail.com> wrote in message 
news:1191678347.256444.152370@k79g2000hse.googlegroups.com...
> Hello everyone,
>
> I am trying to introduce myself to DSP through the free book at
> (www.dspguide.com) on the Internet.
>
> I was studying the chapter on linear systems and it mentions that
> multiplying 2 signals together is not a linear operation. It gives the
> example that when you multiply 2 sinusoids of different frequencies,
> the result is clearly not a sinusoid.
>
> My question is how is that the test for the linearity of the system?
> Why should the multiplication of 2 sinusoids in a linear system
> produce another sinusoid?
>
> I hope I am expressing my query clearly enough... Would really
> appreciate if someone can help me clarify this doubt...

Be a little careful with this.  If both "inputs" are sinusoids then the 
system may be linear time varying or nonlinear.  There is a long thread here 
where Jerry Avins and I and others discussed it at length.

If one of the sinusoids isn't viewed as an "input" but rather part of the 
system and is held constant (e.g. that its amplitude and frequency don't 
change) then relative to the other input, the system passes all the tests 
for linearity - even though "new" frequencies are generated at the output. 
This probably generalizes to any steady-state periodic function in the 
system that multiplies the input to get to the output.

Scaling works.
Superposition works.
etc.
It's just that the output resulting from a simple input is different than 
one might expect from reading about linear systems.  The treatment in the 
literature of linear time varying systems is thin in comparison.

Fred

robert bristow-johnson wrote:
> On Oct 6, 11:18 am, Andor wrote:
>
> > A "system" (*) H is linear iff
>
> > H(a x1  +  b x2)  =  a H(x1)  +  b H(x2)
>
> > for all numbers a and b and all signals x1 and x2 (just showing the
> > above condition to be true for a specific pair of signals will not
> > do).
>
> i.e. *you* don't get to choose a or b or x1 or x2, the devil gets to
> choose those numbers or signals and to establish linearity, you have
> to show that the above superposition equation is true nonetheless.
>
> BTW, the scaling properties,
>
>    H(a x1)  =  a H(x1)
>
> need not be axiomatically part of the criterion for defining
> linearity.  

The scaling property is called "homogeneity". The other property
(breaking up across sums) is called "additivity". Both are needed for
"linearity". Googling these three terms will give you plenty of
examples for the definition of linearity.

> the superposition property
>
>    H(x1  +  x2)  =  H(x1)  +  H(x2)
>
> is sufficient and you can derive the scaling property (for all
> rational "a") directly from the superposition property.  

Can you show me the derivation?

> for
> irrational "a", you have to hand-wave a sorta continuity assumption

Continuity of linear maps is only guaranteed in finite vector spaces.
In functional vector spaces, linear maps need not be continuous (for
example the derivative is not continuous). And this is where we are
applying our linear systems theory.

> (or get utterly anal about measure theory that you get in Real
> Analysis or Advanced Calculus or whatever they're calling it) that is
> perfectly reasonable for physical systems.

I don't see where measure theory comes into this ...

Regards,
Andor

On Oct 8, 3:15 am, Andor <andor.bari...@gmail.com> wrote:
> robert bristow-johnson wrote:
> > On Oct 6, 11:18 am, Andor wrote:
>
> > > A "system" (*) H is linear iff
>
> > > H(a x1  +  b x2)  =  a H(x1)  +  b H(x2)
>
> > > for all numbers a and b and all signals x1 and x2 (just showing the
> > > above condition to be true for a specific pair of signals will not
> > > do).
>
> > i.e. *you* don't get to choose a or b or x1 or x2, the devil gets to
> > choose those numbers or signals and to establish linearity, you have
> > to show that the above superposition equation is true nonetheless.
>
> > BTW, the scaling properties,
>
> >    H(a x1)  =  a H(x1)
>
> > need not be axiomatically part of the criterion for defining
> > linearity.
>
> The scaling property is called "homogeneity". The other property
> (breaking up across sums) is called "additivity". Both are needed for
> "linearity".

no, only the additivity (or "superposition") property is a necessary
axiom for linearity.  the homegeneity property can be derived from it
(and it's easy to do for rational scaling factors).

Superposition is necessary and sufficient for Linearity whereas
Homogeneity is neither necessary nor sufficient for Linearity.  but
Homogeneity is a consequence of Superposition.

> Googling these three terms will give you plenty of
> examples for the definition of linearity.
>
> > the superposition property
>
> >    H(x1  +  x2)  =  H(x1)  +  H(x2)
>
> > is sufficient and you can derive the scaling property (for all
> > rational "a") directly from the superposition property.
>
> Can you show me the derivation?

it's pretty easy (for the *rational* scaling factor a).

1.  first do it for   a = 2     (trivial)

2.  then do it for   a = N     where N is a positive integer.
(inductive)

3.  then do it for   a = N     where N is a negative integer.

4.  then do it for   a = 1/N   for postive integer N.   (do you see
how, Andor?)

5.  then do it for   a = 1/N   for negative integer N.   (same as step
3.)

6.  then do it for   a = M/N   for any integers M and N.

7.  for complex a with rational real and imag parts, it's trivial if
you accept that the imaginary unit can be treated like any other
factor which is what we do when we first define how arithmetic is done
to complex numbers.

8.  for *irrational* a, it's more of a problem, if you're gonna get
anal about it.  that's why i just appeal to the decent and continuous
nature of physical systems in reality that will not react measureably
different between scaling factors of precisely sqrt(2) (dunno how one
would ever know) and
1.41421356237309504880168872420969807856967187537695  . so i'm not
that anal about it (as i am not anal about the Neanderthal engineering
usage of the Dirac delta function).

> > for
> > irrational "a", you have to hand-wave a sorta continuity assumption
>
> Continuity of linear maps is only guaranteed in finite vector spaces.
> In functional vector spaces, linear maps need not be continuous (for
> example the derivative is not continuous). And this is where we are
> applying our linear systems theory.
>
> > (or get utterly anal about measure theory that you get in Real
> > Analysis or Advanced Calculus or whatever they're calling it) that is
> > perfectly reasonable for physical systems.
>
> I don't see where measure theory comes into this ...

it's to deal with this scaling property of linear systems when the
scaling factor is irrational.  given the basic superposition axiom,
you can show it's true for any rational scaling that gets you as close
you want to some given irrational scaling factor.  you approach it
from above the irrational factor ("lim" with a bar over it) and below
the irrational factor ("lim" with a bar under it) and you can show
that as the *difference* between these two rational scaling factors is
approaching zero, that the output of the linear system must also be
approaching zero.

now how do you show, from that, that the output of the linear system
due to the difference from either of the rational scale factors and
the given irrational scale factor also approaches zero?  can we
mathematically conceive of a system where superposition applies all of
the time (an axiom) and where homogeniety applies for all rational
scaling factors (not an axiom, but a result from superposition), but
where the system responds radically different between the cases where
a = sqrt(2) and where a =
1.41421356237309504880168872420969807856967187537695 ?  can there be
such a system, even conceptually?  usually when such a *measurable*
difference can be established, we can find ways to exaggerate that
measurable difference into a radical difference.

r b-j

>>
>> Multiplication with a fixed signal is a linear operation. A
>> "system" (*) H is linear iff
>>
>> H(a x1 + b x2) = a H(x1) + b H(x2)
>>
>> for all a numbers a and b and all signals x1 and x2 (just showing the
>> above condition to be true for a specific pair of signals will not
>> do). Note that the system H takes one signal as an argument: H = H(x).
>> Now what if H multplies its argument by sin(w t)?. You get
>>
>> H(a x1(t) + b x2(t))
>> = sin(w t)(a x1(t)+b x2(t))
>> = a sin(w t) x1(t) + b sin(w t) x2(t)
>> = a H(x1(t)) + b H(x2(t)),
>>
>> so clearly H is a linear system. Systems can be generalized to more
>> than one input or output. In this case you still write
>>
>> y = H(x),
>>
>> but both x(t) and y(t) are vector functions, ie.
>>
>> x(t) = ( x1(t), x2(t) , ..., x_n(t) )
>>
>> and
>>
>> y(t) = ( y1(t), y2(t), ...., y_m(t) ).
>>
>> The linearity condition for such systems is exactly the same as above,
>> except that x1(t) and x2(t) as well as y(t) = H( x(t) ) are vectors.
>> So the simple case of the system H given by
>>
>> y(t) = H(x1(t), x2(t))
>> = x1(t) x2(t),
>
>Shouldn't this be y1(t)y2(t) ???
>>
>> (n=2, m=1), is not linear. Can you prove it?
>
>What are n and m denoting in this case???
>
>Thanks for your reply. Helps a lot.
>
>Anja
>
>>
>> Regards,
>> Andor
>>
>> BTW, forget that single sinusoid in - single sinusoid out linearity
>> test. This is a stronger condition than linearity. For this to be
>> true, you additionally need time-invariance of the system.
>>
>> (*) What is a "system"? Colloquially, it is an operation that takes an
>> input (some signal),  and produces an output (another signal or a
>> number - numbers are also signals).
>
>
>

A linear system has a property that can be expressed mathematically as
below:

If T{} is the operation performed by the system, then

                T{k*x } = k*T{x}, where k= scalar constant, x= signal.

All the definitions of linear systems given above refer to single-input
linear systems.

For a N-input linear system like the one performing a multiplication
operation (2-input), a simple test for linearity would be to give one
input at a time, take the output for each input and add them. If this sum
is equal to the response of the system when all inputs are given
simultaneously, then the system is linear.

For eg., consider a adder. If the 2 i/ps are a and b, 

T{a,b} = a+b.
T{a,0}= a.
T(0,b} = b.

So, T(a,b} = T(a,0} + T{0,b} for all real and complex a,b. This system is
linear.

For a multiplier,
T{a,b} = a * b.
T{a,0} = 0.
T{0,b} =0.

So, T{a,b} != T{a,0} + T{0,b}.

So, this system in nonlinear.
Hope this clears up things better.

It just occured to me that linear operations on real numbers have 0 as the
identitity. Is this correct?

regds,
Karthick.

On 12 Okt., 04:47, "adolf123" <karthic...@ieee.org> wrote:
> >> Multiplication with a fixed signal is a linear operation. A
> >> "system" (*) H is linear iff
>
> >> H(a x1 + b x2) = a H(x1) + b H(x2)
>
> >> for all a numbers a and b and all signals x1 and x2 (just showing the
> >> above condition to be true for a specific pair of signals will not
> >> do). Note that the system H takes one signal as an argument: H = H(x).
> >> Now what if H multplies its argument by sin(w t)?. You get
>
> >> H(a x1(t) + b x2(t))
> >> = sin(w t)(a x1(t)+b x2(t))
> >> = a sin(w t) x1(t) + b sin(w t) x2(t)
> >> = a H(x1(t)) + b H(x2(t)),
>
> >> so clearly H is a linear system. Systems can be generalized to more
> >> than one input or output. In this case you still write
>
> >> y = H(x),
>
> >> but both x(t) and y(t) are vector functions, ie.
>
> >> x(t) = ( x1(t), x2(t) , ..., x_n(t) )
>
> >> and
>
> >> y(t) = ( y1(t), y2(t), ...., y_m(t) ).
>
> >> The linearity condition for such systems is exactly the same as above,
> >> except that x1(t) and x2(t) as well as y(t) = H( x(t) ) are vectors.
> >> So the simple case of the system H given by
>
> >> y(t) = H(x1(t), x2(t))
> >> = x1(t) x2(t),
>
> >Shouldn't this be y1(t)y2(t) ???
>
> >> (n=2, m=1), is not linear. Can you prove it?
>
> >What are n and m denoting in this case???
>
> >Thanks for your reply. Helps a lot.
>
> >Anja
>
> >> Regards,
> >> Andor
>
> >> BTW, forget that single sinusoid in - single sinusoid out linearity
> >> test. This is a stronger condition than linearity. For this to be
> >> true, you additionally need time-invariance of the system.
>
> >> (*) What is a "system"? Colloquially, it is an operation that takes an
> >> input (some signal),  and produces an output (another signal or a
> >> number - numbers are also signals).
>
> A linear system has a property that can be expressed mathematically as
> below:
>
> If T{} is the operation performed by the system, then
>
>                 T{k*x } = k*T{x}, where k= scalar constant, x= signal.

This is correct, but it is not (or only part) of the characteristic of
a linear system. Additivity is more important. In fact, if you read r
b-j's post from October 8 in this thread, it shows that for continuous
linear systems, the homegeneity follows from the additivity. All
linear systems on finite dimensional vector spaces are continuous.
Furthermore, continuity is a sufficient but not a necessary property
for an additive system to also be homogeneous. In signs:

Finite dimensional vector space:
additive <=> linear <=> homogeneous and additive

It is clear that for infinite dimensional vectors space, at least
additive and continuous => linear <=> homogeneous and additive.

It would be interesting to see a counter-example that is additive but
not linear (this counter-example would necessarily be a linear map on
an infinite dimensonal vector space). I couldn't come up with one, but
I couldn't prove the opposite neither.  Perhaps our mathematical
lurker Heinrich knows more about this.

...

> It just occured to me that linear operations on real numbers have 0 as the
> identitity. Is this correct?

What do you mean by identity? Clearly, all linear maps have T(0)=0
(because of the additivity). Is an "identity" a solution to T(x) = x
(this is called a fixed point of T) ?

Regards,
Andor

...
> It would be interesting to see a counter-example that is additive but
> not linear (this counter-example would necessarily be a linear map on
                                                        ^^^^
                                                        non-
> an infinite dimensonal vector space).

...

On Oct 11, 10:47 pm, "adolf123" <karthic...@ieee.org> wrote:
>
> A linear system has a property that can be expressed mathematically as
> below:
>
> If T{} is the operation performed by the system, then
>
>                 T{k*x } = k*T{x}, where k= scalar constant, x= signal.
>

but Karthick, that property is neither sufficient nor necessary.  to
speak to its sufficiency:

 let         T{ x(t) }  =  ( x(t) * x(t-1) )/x(t-2)

that satisfies the scaling property for any k, but the system is not
linear.  as to the sufficiency, it can be shown that if the additivity
property holds (for just two added inputs), what i usually like to
call "superposition":

     T{ x1(t) + x2(t) } = T{ x1(t) } + T{ x2(t) }

     for *any* given x1(t) and x2(t)

if that property holds, you can easily show that the scaling property
holds

     T{k*x } = k*T{x}

for any *rational* k.  it's a little harder to do for the irrational
k, which requires an additional assumption about the continuous nature
of the system T{..}, but an assumption i have no problem with
regarding decent, physical systems.   it's a real wild-assed system
that would react significantly different if k = pi vs. k =
3.141592654 .  i'm still wondering how i would define such a wild-
assed system, unless i make use of some wild-assed function like:

    f(x) = 1 for rational x and f(x) = 0 for irrational x.

but i dunno of a physical system that can do something like that.

r b-j