Sunday, December 1, 2013
The perils of dividing by zero
In a middle school math competition a few years ago, the following question was asked: given an n by m matrix of numbers whose average row sum is R and average column sum is C, what is the ratio R/C. Since R = T/n and C = T/m, where T is the sum of all the entries in the matrix, it would appear that R/C = m/n. This is the expected answer for this question and is correct in almost all cases. But one must be careful when dividing by a number to ensure that the divisor is not zero. We assume the matrix is nondegenerate, i.e. m > 0 and n > 0, so dividing by n and m is okay and R, C are well-defined. However, it is possible that C = 0, in which case R/C is not well-defined. This cases occurs when T = 0, in which case R is also 0. A simple example is when the matrix consists of all zeros. The use of undefined operations such as dividing by 0 can lead to an alleged "proof" of 1 = 2 which is not good as we do not want an inconsistent theory.
Thursday, November 28, 2013
Opposing views
The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel in 2013 was awarded to Eugene Fama, Lars Peter Hansen and Robert Schiller. In an article in the New York Times, Professor Schiller commented on how he disagrees with the other 2 winners of the Prize even though they are all cited for their work on "empirical analysis of asset prices". This reminds me that in virtually all sciences, even in hard sciences such as physics, there are disagreements on the validity of various theories. One notable exception is in mathematics, where a formal proof of a theorem from antiquity is still accepted today. Of course there are disagreements in mathematics, such as whether the proof of the four color theorem is valid, since it was only checkable using a computer program, but that is a debate whether there is a mistake in the proof, not whether the proof methodology is invalid. Mathematical logic is a branch of mathematics that contemplates questions about consistency and completeness of formal mathematical proofs. For instance, is it possible to provide a formal proof of a statement and its negation? Consistent theories means that you cannot prove both a statement and its negation. A complete theory means that for every statement you can prove the statement or its negation. Most practicing mathematicians are probably not worried much about consistency and completeness of the mathematical framework they are working in, they just assume that it is consistent and complete. It was quite a shock when Kurt Gödel proved in 1931 that various models of arithmetic are incomplete, i.e. there are true statements about natural numbers that cannot be proven with these axiomatic theories.
Sunday, October 27, 2013
Orange and orange
In a previous post, I looked at the sound for the word tea and the letter T in various European languages and found that they are the same in several languages. Recently I noticed that the fruit "orange" and the color "orange" are described by the same word in English. In what other languages are they described by the same word?
This is true in Chinese (both Mandarin and Cantonese), Spanish and French, but not Dutch. In the Dutch language, the color is called oranje (coincidentally orange is the national color of the Netherlands because it is also the name of the Dutch Royal family, derived from the name of a French principality belonging to their ancestor Willem de Zwijger), while the fruit is called sinaasappel or appelsien. I wonder what other languages have different words for these two concepts as well?
This is true in Chinese (both Mandarin and Cantonese), Spanish and French, but not Dutch. In the Dutch language, the color is called oranje (coincidentally orange is the national color of the Netherlands because it is also the name of the Dutch Royal family, derived from the name of a French principality belonging to their ancestor Willem de Zwijger), while the fruit is called sinaasappel or appelsien. I wonder what other languages have different words for these two concepts as well?
Saturday, October 26, 2013
Theorem of the alternative and logical equivalence
In the theory of linear equalities and inequalities, several fundamental results are formulated as a theorem of the alternative: two alternatives are given, and exactly one of the alternatives is satisfied at any one time. A well known example is Farkas' lemma (1894):
For a real matrix $A$ and real vector $b$, exactly one of the following conditions is true:
where we say a real vector is (non)negative if all its entries are (non)negative. Consider a theorem of the alternative given in the following form: given two alternatives $P$ or $Q$, only one of them is true at any time, no more and no less. The truth table for this conclusion (denoted as $Z$) is then:
This means that $Z$ is equal to $P\oplus Q$ which is equivalent to $P\Leftrightarrow \neg Q$ which is equivalent to $\neg P\Leftrightarrow Q$.
Thus the theorem
Exactly one of the two statements $P$ and $Q$ is true
can also be restated as:
P is true if and only if Q is false
or as:
P is false if and only if Q is true
Setting the 2 statements in Farkas' Lemma above as $P$ and $Q$, then
$P\Leftrightarrow \neg Q$ is written as
Let $A$ be a real matrix and let $b$ be a real vector. Then there exists a nonnegative real vector $x$ such that $Ax=b$ if and only if for each row vector $y$ either $yA$ is not a nonnegative vector or $yb$ is nonnegative.
Given that $P\Rightarrow Q$ is logically equivalent to $\neg P \vee Q$, this can be rewritten as
Let $A$ be a real matrix and let $b$ be a real vector. Then there exists a nonnegative real vector $x$ such that $Ax=b$ if and only if $yb$ is nonnegative for each row vector $y$ such that $yA$ is a nonnegative vector.
which is the form of Farkas' Lemma as stated in A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.
For a real matrix $A$ and real vector $b$, exactly one of the following conditions is true:
- There exists a real nonnegative vector $x$ such that $Ax = b$
- There exists a real row vector y such that $yA$ is nonnegative and $yb$ is negative.
where we say a real vector is (non)negative if all its entries are (non)negative. Consider a theorem of the alternative given in the following form: given two alternatives $P$ or $Q$, only one of them is true at any time, no more and no less. The truth table for this conclusion (denoted as $Z$) is then:
| P | Q | Z |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
This means that $Z$ is equal to $P\oplus Q$ which is equivalent to $P\Leftrightarrow \neg Q$ which is equivalent to $\neg P\Leftrightarrow Q$.
Thus the theorem
Exactly one of the two statements $P$ and $Q$ is true
can also be restated as:
P is true if and only if Q is false
or as:
P is false if and only if Q is true
Setting the 2 statements in Farkas' Lemma above as $P$ and $Q$, then
$P\Leftrightarrow \neg Q$ is written as
Let $A$ be a real matrix and let $b$ be a real vector. Then there exists a nonnegative real vector $x$ such that $Ax=b$ if and only if for each row vector $y$ either $yA$ is not a nonnegative vector or $yb$ is nonnegative.
Given that $P\Rightarrow Q$ is logically equivalent to $\neg P \vee Q$, this can be rewritten as
Let $A$ be a real matrix and let $b$ be a real vector. Then there exists a nonnegative real vector $x$ such that $Ax=b$ if and only if $yb$ is nonnegative for each row vector $y$ such that $yA$ is a nonnegative vector.
which is the form of Farkas' Lemma as stated in A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.
Wednesday, October 16, 2013
Gravity
Over the weekend, my family and I went to see the movie "Gravity" in IMAX 3D after hearing all the buzz about it. Admittedly there are some scientific errors in the movie (my son was whispering to me during the movie why Clooney needs to detach himself from Bullock to save her), the movie was a thrilling ride and made you feel what it is like to be adrift in space. I have always been fascinated by spaceflight ever since I read the books "The right stuff" and "2001: a space odyssey" (I have also seen the movies, of course) as a boy. The movie also reminds me of a common misconception we have when we see footage of astronauts in space: that there is no gravity in space (hence the term "zero gravity"). We see that as soon as the spacecraft escapes Earth's atmosphere, things like pens start to float around in the capsule. While is it true that in deep space, far away from other celestial bodies, the effect of their gravitational pull can be minuscule, all manned spaceflights are still relatively close to Earth and will feel its gravitational pull.
Consider astronauts at the International Space Station (ISS). They experience a gravitational pull similar in strength to what we experience on the ground. Recall Sir Isaac Newton's celebrated equation describing the forces between two bodies:
$$ F = \frac{Gm_1m_2}{r^2}$$
where $G\approx 6.67384 \times 10^{-14}m^3g^{-1}s^{-2}$.
Using Newton's second law of motion $F=ma$, the acceleration an object is subjected to due to another object with mass $m$ and a distance $r$ away is $\frac{Gm}{r^2}$. To calculate the acceleration induced by the gravitational force you feel from the Earth, if we assume the Earth is a sphere with a spherically symmetric density, then $r$ is the distance between you and the center of the Earth, approximately 6.371 Mm. The mass of the Earth $M_e$ is approximately $5.972\times 10^{27}g$, resulting in a constant $ \frac{G M_e}{r^2} \approx 9.82 ms^{-2}$.
The ISS is about 0.37 Mm above the ground, increasing $r$ to be about 6.731 Mm. The resulting constant is then approximately $8.8$, a 10% reduction in weight for everyone on board. However, the astronauts do not feel this force as they are orbiting the Earth, as they are essentially in continuous free fall. In other words, without gravity, the spacecraft would move in a straight line, and the speed of the spacecraft is such that the acceleration needed to change the trajectory to an orbit around the Earth is exactly equal to the acceleration induced by the gravitational force. It is a nice exercise in calculus (which by the way was also invented by Isaac Newton through his introduction of Fluxions and Fluents) to show this.
Since everything is relative, we must also note that we (along with the Earth) are orbiting the Sun as well at a speed of over 100Mm/hr. The distance from the Earth to the Sun is approximately $1.496\times 10^{11}m$ and the mass of the Sun is approximately $1.989\times 10^{33}g$. Applying Newton's formula above, we get $ \frac{G M_s}{r^2} \approx 0.00593$, which is much smaller than the constant for Earth. Since we and the Earth are in the same orbit (and thus in free fall) around the Sun, we do not notice the effects of the Sun's gravitational pull.
When I told my wife that we are moving around the Sun at high speed, she quipped "So we don't have a sedentary lifestyle then."
Consider astronauts at the International Space Station (ISS). They experience a gravitational pull similar in strength to what we experience on the ground. Recall Sir Isaac Newton's celebrated equation describing the forces between two bodies:
$$ F = \frac{Gm_1m_2}{r^2}$$
where $G\approx 6.67384 \times 10^{-14}m^3g^{-1}s^{-2}$.
Using Newton's second law of motion $F=ma$, the acceleration an object is subjected to due to another object with mass $m$ and a distance $r$ away is $\frac{Gm}{r^2}$. To calculate the acceleration induced by the gravitational force you feel from the Earth, if we assume the Earth is a sphere with a spherically symmetric density, then $r$ is the distance between you and the center of the Earth, approximately 6.371 Mm. The mass of the Earth $M_e$ is approximately $5.972\times 10^{27}g$, resulting in a constant $ \frac{G M_e}{r^2} \approx 9.82 ms^{-2}$.
The ISS is about 0.37 Mm above the ground, increasing $r$ to be about 6.731 Mm. The resulting constant is then approximately $8.8$, a 10% reduction in weight for everyone on board. However, the astronauts do not feel this force as they are orbiting the Earth, as they are essentially in continuous free fall. In other words, without gravity, the spacecraft would move in a straight line, and the speed of the spacecraft is such that the acceleration needed to change the trajectory to an orbit around the Earth is exactly equal to the acceleration induced by the gravitational force. It is a nice exercise in calculus (which by the way was also invented by Isaac Newton through his introduction of Fluxions and Fluents) to show this.
Since everything is relative, we must also note that we (along with the Earth) are orbiting the Sun as well at a speed of over 100Mm/hr. The distance from the Earth to the Sun is approximately $1.496\times 10^{11}m$ and the mass of the Sun is approximately $1.989\times 10^{33}g$. Applying Newton's formula above, we get $ \frac{G M_s}{r^2} \approx 0.00593$, which is much smaller than the constant for Earth. Since we and the Earth are in the same orbit (and thus in free fall) around the Sun, we do not notice the effects of the Sun's gravitational pull.
When I told my wife that we are moving around the Sun at high speed, she quipped "So we don't have a sedentary lifestyle then."
Saturday, September 28, 2013
A short tutorial of nonlinear circuit theory - part 2
In a previous post, we look at Kirchoff's laws and device constituency relations to derive state equations of an electrical circuit. Today we will look at some simple circuits and their corresponding state equations. The simplest dynamic circuit must have at least one capacitor (or inductor). Let us consider a circuit with one linear capacitor and one nonlinear resistor.
The state equations can then be written as
\begin{equation} \frac{dq}{dt} = -g(v) = -g(q/C) \end{equation}
The trajectories can be visualized on the dynamic route, where we plot $\frac{dq}{dt}$ against $q$ and the arrows indicate how the trajectory will evolve:
How do we resolve such nonphysical situations? By adding parasitic elements. Suppose we add a parasitic inductor L in series to the nonlinear resistor.
The resulting state equations will be given by: \[ \begin{array}{lcl}\frac{dq}{dt} & = & i_L = \frac{\phi}{L} \\ \frac{d\phi}{dt} & = & v_L = v_R - v_C = f(i_R) - q/c = f(\phi/L) - q/c \end{array} \]
By introducing the variable $i_C = -i_L = -\phi/L$ we get the state equations: \[ \begin{array}{lcl}\frac{dq}{dt} & = & i_C \\ \frac{di_C}{dt} & = & -\frac{1}{L}(q/C - f(-i_C)) \end{array} \] By drawing the phase portrait, we see that at the curve $q = Cf(-i_C)$, $di_C/dt = 0$. In fact, we have an oscillator.
For the nonlinear resistor with a constituency relation as shown above, the existence of the limit cycle can be proved more rigorously by using the Poincaré -Bendixson theorem and the fact that the system has a bounded trapping region and a single equilibrium point that is unstable.
For $f$ an odd function, a second order system in this form is a Liénard equation [5] and the Levinson-Smith theorem [6] allows us to prove the existence of a stable limit cycle when the nonlinear resistor is of a certain form:
Theorem [Levinson-Smith 1942]: Consider the second order equations
\[ \begin{array}{lcl} dx/dt & = & y - F(x) \\ dy/dt & = & -g(x) \end{array} \] Suppose that
Note that our circuit above satisfies the hypothesis of the Levinson-Smith theorem if our nonlinear resistor has the form $v = f(i)$ where $f$ is a cubic polynomial of the form $x^3-ax$ for $a>0$. In particular, we get exactly the Van der Pol equation $x'' + \alpha (x^2-1)x' + x = 0$ [8], an equation used to model oscillations occurring in a circuit involving vacuum tubes.
Another condition for guaranteeing the existence of a unique periodic solution is the following result [7]:
Theorem: Consider the second order equations
\[ \begin{array}{lcl} dx/dt & = & y - F(x) \\ dy/dt & = & -g(x) \end{array} \] Suppose that
References:
[1] L. O. Chua, Introduction to nonlinear network theory, McGraw-Hill, 1969.
[2] L. O. Chua, C. A. Desoer, E. S. Kuh, Linear and nonlinear circuits, McGraw-Hill, 1987.
[3] L. O. Chua, Memristor-The missing circuit element, IEEE Transactions on Circuit Theory, Sept. 1971, vol. 18, no. 5, pp. 507-519.
[4] D. B. Strukov, G. S. Snider, D. R. Stewart1 & R. S. Williams, The missing memristor found, Nature 453, 1 May 2008, pp. 80-83.
[5] A. Liénard, Étude des oscillations entretenues, Revue génér. de l'électr. 23, (1928), 901 - 902; 906 - 954.
[6] N. Levinson, O. Smith, A general equation for relaxation oscillations Duke Math. J. 9, (1942), 382 - 403.
[7] D. W. Jordan and P. Smith, Nonlinear Ordinary Differential Equations, Oxford University Press, 1977.
[8] Van der Pol, B. and Van der Mark, J., Frequency demultiplication, Nature, vol. 120, pp. 363-364, 1927.
Case 1: Assume that the resistor is voltage-controlled ($i = g(v)$)
The state equations can then be written as
\begin{equation} \frac{dq}{dt} = -g(v) = -g(q/C) \end{equation}
The trajectories can be visualized on the dynamic route, where we plot $\frac{dq}{dt}$ against $q$ and the arrows indicate how the trajectory will evolve:
Case 2: assume that the resistor is current controlled ($v = f(i)$).
We have $v = f(i) = f(-dq/dt)$. Since $v = q/C$ we get $q = Cf(-dq/dt)$. Using the dynamic route interpretation and depending on the shape of $f$, it is possible to find impasse points, where the trajectory does not know what to do.
How do we resolve such nonphysical situations? By adding parasitic elements. Suppose we add a parasitic inductor L in series to the nonlinear resistor.
The resulting state equations will be given by: \[ \begin{array}{lcl}\frac{dq}{dt} & = & i_L = \frac{\phi}{L} \\ \frac{d\phi}{dt} & = & v_L = v_R - v_C = f(i_R) - q/c = f(\phi/L) - q/c \end{array} \]
By introducing the variable $i_C = -i_L = -\phi/L$ we get the state equations: \[ \begin{array}{lcl}\frac{dq}{dt} & = & i_C \\ \frac{di_C}{dt} & = & -\frac{1}{L}(q/C - f(-i_C)) \end{array} \] By drawing the phase portrait, we see that at the curve $q = Cf(-i_C)$, $di_C/dt = 0$. In fact, we have an oscillator.
For the nonlinear resistor with a constituency relation as shown above, the existence of the limit cycle can be proved more rigorously by using the Poincaré -Bendixson theorem and the fact that the system has a bounded trapping region and a single equilibrium point that is unstable.
For $f$ an odd function, a second order system in this form is a Liénard equation [5] and the Levinson-Smith theorem [6] allows us to prove the existence of a stable limit cycle when the nonlinear resistor is of a certain form:
Theorem [Levinson-Smith 1942]: Consider the second order equations
\[ \begin{array}{lcl} dx/dt & = & y - F(x) \\ dy/dt & = & -g(x) \end{array} \] Suppose that
- $F$ is an odd $C^1$ function (i.e. $F(-x) = -F(x)$),
- $g$ is an odd $C^0$ function with $xg(x)>0$ for all $x\neq 0$,
- There is a constant $a>0$ such that $F(x) < 0$ on $0 < x < a$, $F(x) > 0$ on $x > a$, and $F'(x) > 0$ on $x>a$,
- $\int_0^x g(s)ds \rightarrow\infty$ as $|x|\rightarrow \infty$ and $F(x) \rightarrow\infty$ as $x\rightarrow \infty$.
Note that our circuit above satisfies the hypothesis of the Levinson-Smith theorem if our nonlinear resistor has the form $v = f(i)$ where $f$ is a cubic polynomial of the form $x^3-ax$ for $a>0$. In particular, we get exactly the Van der Pol equation $x'' + \alpha (x^2-1)x' + x = 0$ [8], an equation used to model oscillations occurring in a circuit involving vacuum tubes.
Another condition for guaranteeing the existence of a unique periodic solution is the following result [7]:
Theorem: Consider the second order equations
\[ \begin{array}{lcl} dx/dt & = & y - F(x) \\ dy/dt & = & -g(x) \end{array} \] Suppose that
- $F$ is an odd $C^1$ function and is zero only at $x=0$,$x=a$ and $x=-a$ for some $a>0$,
- $F(x) \rightarrow \infty$ monotonically as $x\rightarrow \infty$ for $x >a$.
- $g$ is an odd $C^0$ function with $xg(x)>0$ for all $x\neq 0$,
References:
[1] L. O. Chua, Introduction to nonlinear network theory, McGraw-Hill, 1969.
[2] L. O. Chua, C. A. Desoer, E. S. Kuh, Linear and nonlinear circuits, McGraw-Hill, 1987.
[3] L. O. Chua, Memristor-The missing circuit element, IEEE Transactions on Circuit Theory, Sept. 1971, vol. 18, no. 5, pp. 507-519.
[4] D. B. Strukov, G. S. Snider, D. R. Stewart1 & R. S. Williams, The missing memristor found, Nature 453, 1 May 2008, pp. 80-83.
[5] A. Liénard, Étude des oscillations entretenues, Revue génér. de l'électr. 23, (1928), 901 - 902; 906 - 954.
[6] N. Levinson, O. Smith, A general equation for relaxation oscillations Duke Math. J. 9, (1942), 382 - 403.
[7] D. W. Jordan and P. Smith, Nonlinear Ordinary Differential Equations, Oxford University Press, 1977.
[8] Van der Pol, B. and Van der Mark, J., Frequency demultiplication, Nature, vol. 120, pp. 363-364, 1927.
Sunday, September 15, 2013
How to eat a meal
Many times my family and I face a dilemma when we go to a restaurant for a meal. We would order a few dishes and when the food arrives we need to solve the following problem: there are several types of food on the table, each with a different preference in our mind. The question then is: which food should we eat first, which food should we eat second, etc. My strategy is to eat my favorite food first. My wife has a different philosophy; she saves the best for last. I don't agree with her as I believe that your favorite food will not taste as good at the end of a meal, much more so than for food that you do not like as much anyway. Attempting to formulate this as a mathematical problem, we are essentially maximizing our enjoyment of the meal:
$$ \max_S E(S)$$
where $F$ is the set of food items on the table, $S = (s_1,s_2,s_3,...)$ is the sequence of food to eat subject to the constraint that $s_i\in F$ and $E$ is your enjoyment of your meal based on the sequence $S$. The function $E$ can have very different forms depending on the individual and there are additional constraints depending on the situation. Do you have to eat every items in $F$, or do you eat until you are full and put the leftovers in a doggie bag? Is there a time constraint, in which case certain foods can be more easily digested and thus enjoyed more? This problem can also be defined in more complicated ways by allowing you to eat part of one food item before eating part of another food item, etc. $E(S)$ can simply be $E(S) = \sum_i E_i(s_i)$ where $E_i$ becomes smaller for larger $i$ as you are getting full, i.e. for all $x\in F$, $E_i(x)< E_j(x)$ if $i>j$. My argument at the beginning of this post was that $E_i$ decreases faster proportionally as $i$ increases for my favorite food than for foods I dislike. To complicate things further, the ordering of the food items can influence your enjoyment not simply because your stomach is getting fuller, but could also depend on the flavor involved. Eating something sour might increase your appetite, whereas according to my wife eating something sweet after eating something salty might make you want to eat more salty foods. The use of sorbet to clean your palate between courses is another indication of this phenomenon. Similarly, eating protein or eating food that requires you to chew more will make you satisfied sooner. When presented with a plate of various fruits, she will eat the most sour fruits first, since she believes eating a sweet fruit first will make eating the sour fruit taste even more sour.
How different is the function $E$ different from person to person? Can we use our eating strategy $S$ over various meals to deduce the (presumably hidden) utility function $E$? (assuming that we are mentally optimizing $E$.) Can optimizing $E$ be used to satisfy weight-loss goals?
$$ \max_S E(S)$$
where $F$ is the set of food items on the table, $S = (s_1,s_2,s_3,...)$ is the sequence of food to eat subject to the constraint that $s_i\in F$ and $E$ is your enjoyment of your meal based on the sequence $S$. The function $E$ can have very different forms depending on the individual and there are additional constraints depending on the situation. Do you have to eat every items in $F$, or do you eat until you are full and put the leftovers in a doggie bag? Is there a time constraint, in which case certain foods can be more easily digested and thus enjoyed more? This problem can also be defined in more complicated ways by allowing you to eat part of one food item before eating part of another food item, etc. $E(S)$ can simply be $E(S) = \sum_i E_i(s_i)$ where $E_i$ becomes smaller for larger $i$ as you are getting full, i.e. for all $x\in F$, $E_i(x)< E_j(x)$ if $i>j$. My argument at the beginning of this post was that $E_i$ decreases faster proportionally as $i$ increases for my favorite food than for foods I dislike. To complicate things further, the ordering of the food items can influence your enjoyment not simply because your stomach is getting fuller, but could also depend on the flavor involved. Eating something sour might increase your appetite, whereas according to my wife eating something sweet after eating something salty might make you want to eat more salty foods. The use of sorbet to clean your palate between courses is another indication of this phenomenon. Similarly, eating protein or eating food that requires you to chew more will make you satisfied sooner. When presented with a plate of various fruits, she will eat the most sour fruits first, since she believes eating a sweet fruit first will make eating the sour fruit taste even more sour.
How different is the function $E$ different from person to person? Can we use our eating strategy $S$ over various meals to deduce the (presumably hidden) utility function $E$? (assuming that we are mentally optimizing $E$.) Can optimizing $E$ be used to satisfy weight-loss goals?
Saturday, September 14, 2013
Fireworks and the speed of sound
We were watching a fireworks display during our spring break vacation this year, and my son remarked that there is a delay in the sound that we hear from the fireworks that we see in the air. Since the fireworks typically go off quite high in the sky, the delay can be a second or more. (This is the same reason why we see lightning before hearing the thunder and we can use the delay to estimate how far the lightning strike is.) Recall that the speed of sound is about 340 m/s and the speed of light is so high (about 300 Mm/s) that the delay is essentially the time it takes for the sound to reach our ears. I have never thought of that before, mainly because in a fireworks display many fireworks are going off at different times close to each other and this masks the delay phenomenon. After he mentioned it, I notice it now every time I watch fireworks (and there are many opportunities during the year) and makes me realize that the perfectly synchronized sound effects you hear in a movie when they have a fireworks display may not be accurate.
Saturday, September 7, 2013
A short tutorial of nonlinear circuit theory - part 1
Today we look at applications of dynamical system theory in electrical engineering. How is dynamical systems important for electrical engineering? At the most fundamental level, electrical engineering deals with the physics of electricity. We can describe electrical and magnetic phenomena via Maxwell's equations and the interaction of electrons, ions, and protons in physical matter. Such mathematical models in general give us partial differential equations. However, if we describe things in such detail, the resulting equations will be so complicated that either it takes a long time to simulate the system or very little useful information can be extracted from the equations. Therefore in many electrical circuit applications, we will assume the lumped circuit approximation. In a lumped circuit, electrical signals are propagated instantaneously through wires. Exceptions to this approximation occur in applications such as high speed electronics and wireless electronics. What follows is a brief introduction to nonlinear circuit theory. A more in depth study can be found in Ref. [1] and Ref. [2]. In general an electrical circuit consists of devices connected with wires. Because of the lumped circuit approximation, the lengths of the wires are irrelevant. Each device can be thought of as a black box with n terminals, in which case it is called an n-terminal device. For example, a resistor or a capacitor is a 2-terminal device and a transistor is a 3-terminal device. Depending on our level of abstraction, a device could be a transistor, an amplifier consisting of many transistors, or a complicated device such as a microprocessor with billions of transistors. Each n -terminal device can be represented by a digraph with n branches connected at the datum node (Fig. 1).
Resistive and dynamic 2-terminal devices
In this short introduction we will only focus on electrical circuits composed of 2-terminal devices. The two most important physical quantities in electrical circuits are voltages (v) and currents (i). Two related quantities are the electrical flux linkage ($\phi$) and charge (q) which are related to v and i via:
\[ i = \frac{dq}{dt},\qquad v = \frac{d\phi}{dt}
\]
A 2-terminal device has two terminals and can be represented abstractly as a digraph with one branch and an associated reference direction:
A device which relates the voltage across it and the current through it is called a resistor. In particular, it is described by the constituency relation $R(v,i) = 0$. A device which relates the charge on it with the voltage across it is called a capacitor and is described by the constituency relation $C(q,v) = 0$. A device which relates the flux linkage across it with the current through it is called an inductor and is described by $L(\phi,i) = 0$. A resistor is called voltage-controlled if the constituency relation can be written as a function of voltage, i.e. $i = f(v)$. Similar definitions exist for current-controlled resistors, charge-controlled capacitors etc. Resistors are static devices while capacitors and inductors are dynamic devices. As we will see shortly, a circuit without dynamic devices has no dynamics. The introduction of dynamic devices allow us to describe the behavior of the circuit as a continuous-time dynamical system.
What about a device which relates flux linkage and charge via a relation $M(\phi, q) = 0$? Such devices are called memristors (MEMory ResISTOR) as postulated by Leon Chua in 1971 (Ref. [3]). Even though such devices can be synthesized using transistors and amplifiers, an elementary implementation did not exist until Stan Williams and his team from HP developed memristors using titanium dioxide in 2008 (Ref. 4).
Kirchoff's Laws
A electrical circuit can be represented abstractly as a digraph with a branch current and branch voltage associated to each branch. We assume that the circuit is connected, i.e. the corresponding digraph is (weakly) connected (though not necessarily strongly connected). Consider a connected digraph with n nodes and b branches. Since the digraph is connected, $b\geq n-1$. The node-edge incidence matrix (or just incidence matrix) associated to a digraph is an n by b matrix A such that $A_{jk} = 1$ if branch k leaves node j, $A_{jk} = -1$ if branch k enters node j, and $0$ otherwise.
Kirchoff's laws describe the relationships which these currents and voltages need to satisfy due to physical constraints such as charge conservation.
Kirchoff's current law (KCL) states that the sum of the currents entering a node is equal to the sum of the currents leaving the node. A moment's thought will convince you that this requirement for the j-th node corresponds to the product between the j-th row of A and the current vector i be equal to 0. Thus Kirchoff's current law can be stated as Ai = 0.
Theorem: the matrix A has rank n-1.
Proof: the i-th column of A consist of exactly one entry 1 and one entry -1 corresponding to the nodes that branch i is connected to. Consider k rows of A with k. Suppose a linear combination of these equations with nonzero coefficients sums to zero. Since the graph is connected, there is a node m which is connected by a branch to a node in these k nodes. The corresponding column in A has a 1 (or -1) in the m-th row and a -1 (or 1) in a row belonging to the k rows. Therefore a linear combination of these equations with nonzero coefficients cannot sums to zero. This show that the rank of A is at least n-1. The sum of the rows of A is zero, so A cannot be full rank, and thus the rank of A is exactly n-1. $\blacksquare$
Thus we can delete one row from A without losing any information since this row is always a linear combination of the other rows. In the following we assume that A is a n-1 by b matrix with rank n-1.
For a branch k which goes between nodes $j_1$ and $j_2$, Kirchoff's voltage law (KVL) states that the voltage $v_k$ across branch k is equal to the difference $e_{j_1}-e_{j_2}$ where $e_{j}$ is the voltage between the j-th node and the datum node. It is easy to see that Kirchoff's voltage law can be expressed as $A^T$e-v = 0 or $A^T$e = v.
Thus $v$ is in the range of the matrix $A^T$. Since $A^T$ has rank n-1, another way to say this is that v lies in a n-1-dimensional subspace of ${\Bbb R}^b$. Thus we can also express KVL using the orthogonality conditon Bv = 0 where B is a b-(n-1) by b matrix. One such matrix B is the fundamental loop matrix and describes a set of b-(n-1) loops in the circuit from which all loops in the circuit can be derived. This is another way to view KVL: the algebraic sum of branch voltages in a loop is 0.
The complete description of the electronic circuit can be given by KVL, KCL, the constituency relations of the elements and the defining equations $i = \frac{dq}{dt}$ and $v = \frac{d\phi}{dt}$. This gives us a set of constrained differential equations which describes the system. It is not always possible to obtain a set of ordinary differential equations. In the case that we can, it will be given in the form
\begin{equation}\label{eqn:state_circuit} \begin{array}{lclr}
\frac{dq}{dt} & =& f_1(q,\phi) & \qquad \mbox{Eq.} (1)\\
\frac{d\phi}{dt} & = & f_2(q,\phi) & \end{array}
\end{equation}
where q is the charge vector corresponding to the charges of all the capacitors and $\phi$ is the flux vector corresponding to the flux of the inductors. The state vector is $(q,\phi)$. In the case where the capacitors and inductors are linear, we have q = Cv and $\phi = Li$, so for $C\neq 0$ and $L\neq 0$, we can also choose $(v,i)$ as the state vector. This is more desirable since voltages and currents can be more easily measured. Furthermore, this change of variables can be also be done if there is a diffeomorphism between q and v and between $\phi$ and i. The system defined by (v,i) is topologically conjugate to Eq. (1) via the diffeomorphism. The number of equations in Eq. (1) will correspond the the total number of capacitors and inductors since we only have 2-terminal capacitors and inductors.
When there are no dynamic elements the circuit is called a resistive circuit and the equations of the circuit are given by Ai=0, Bv = 0 and R(i,v) = 0. This is a set of nonlinear equations, the solutions of which define the operating voltages and currents of the circuit. There is no dynamics in this system. A solution of these equations is an operating point of the circuit and corresponds to the actual voltages and currents we observe in the circuit.
Now a circuit with more than one operating point presents somewhat of a problem. What does the physical circuit choose as the operating point? In practice, the circuit can be at different operating points depending on when or how you power on the system. To resolve this problem we postulate that parasitic capacitances and inductors are present in parallel and series respectively which results in a dynamic circuit. Consider the state equations (Eq. (1)). The equilibrium points correspond to points when $dq/dt = 0$ for the capacitors and $d\phi/dt = 0$ for the inductors. This corresponds to the capacitor currents equal to zero and inductor voltages equal to zero. Thus we can replace capacitors by a open circuit and inductors by a short circuit which results in the original resistive circuit.
Thus the operating points of the resistive circuit corresponds to equilibrium points of the dynamic circuit and initial conditions play a role in what equilibrium point we will see at steady state (assuming that the state trajectory of the dynamic circuit does converge to an equilibrium point) which corresponds to the operating point we observe.
In part 2, we will look at some simple circuits and their corresponding state equations.
[1] L. O. Chua, Introduction to nonlinear network theory, McGraw-Hill, 1969.
[2] L. O. Chua, C. A. Desoer, E. S. Kuh, Linear and nonlinear circuits, McGraw-Hill, 1987.
[3] L. O. Chua, Memristor-The missing circuit element, IEEE Transactions on Circuit Theory, Sept. 1971, vol. 18, no. 5, pp. 507-519.
[4] D. B. Strukov, G. S. Snider, D. R. Stewart1 & R. S. Williams, The missing memristor found, Nature 453, 1 May 2008, pp. 80-83.
Figure 1
In this short introduction we will only focus on electrical circuits composed of 2-terminal devices. The two most important physical quantities in electrical circuits are voltages (v) and currents (i). Two related quantities are the electrical flux linkage ($\phi$) and charge (q) which are related to v and i via:
\[ i = \frac{dq}{dt},\qquad v = \frac{d\phi}{dt}
\]
A 2-terminal device has two terminals and can be represented abstractly as a digraph with one branch and an associated reference direction:
A device which relates the voltage across it and the current through it is called a resistor. In particular, it is described by the constituency relation $R(v,i) = 0$. A device which relates the charge on it with the voltage across it is called a capacitor and is described by the constituency relation $C(q,v) = 0$. A device which relates the flux linkage across it with the current through it is called an inductor and is described by $L(\phi,i) = 0$. A resistor is called voltage-controlled if the constituency relation can be written as a function of voltage, i.e. $i = f(v)$. Similar definitions exist for current-controlled resistors, charge-controlled capacitors etc. Resistors are static devices while capacitors and inductors are dynamic devices. As we will see shortly, a circuit without dynamic devices has no dynamics. The introduction of dynamic devices allow us to describe the behavior of the circuit as a continuous-time dynamical system.
What about a device which relates flux linkage and charge via a relation $M(\phi, q) = 0$? Such devices are called memristors (MEMory ResISTOR) as postulated by Leon Chua in 1971 (Ref. [3]). Even though such devices can be synthesized using transistors and amplifiers, an elementary implementation did not exist until Stan Williams and his team from HP developed memristors using titanium dioxide in 2008 (Ref. 4).
Kirchoff's Laws
A electrical circuit can be represented abstractly as a digraph with a branch current and branch voltage associated to each branch. We assume that the circuit is connected, i.e. the corresponding digraph is (weakly) connected (though not necessarily strongly connected). Consider a connected digraph with n nodes and b branches. Since the digraph is connected, $b\geq n-1$. The node-edge incidence matrix (or just incidence matrix) associated to a digraph is an n by b matrix A such that $A_{jk} = 1$ if branch k leaves node j, $A_{jk} = -1$ if branch k enters node j, and $0$ otherwise.
Kirchoff's laws describe the relationships which these currents and voltages need to satisfy due to physical constraints such as charge conservation.
Kirchoff's current law (KCL) states that the sum of the currents entering a node is equal to the sum of the currents leaving the node. A moment's thought will convince you that this requirement for the j-th node corresponds to the product between the j-th row of A and the current vector i be equal to 0. Thus Kirchoff's current law can be stated as Ai = 0.
Theorem: the matrix A has rank n-1.
Proof: the i-th column of A consist of exactly one entry 1 and one entry -1 corresponding to the nodes that branch i is connected to. Consider k rows of A with k
Thus we can delete one row from A without losing any information since this row is always a linear combination of the other rows. In the following we assume that A is a n-1 by b matrix with rank n-1.
For a branch k which goes between nodes $j_1$ and $j_2$, Kirchoff's voltage law (KVL) states that the voltage $v_k$ across branch k is equal to the difference $e_{j_1}-e_{j_2}$ where $e_{j}$ is the voltage between the j-th node and the datum node. It is easy to see that Kirchoff's voltage law can be expressed as $A^T$e-v = 0 or $A^T$e = v.
Thus $v$ is in the range of the matrix $A^T$. Since $A^T$ has rank n-1, another way to say this is that v lies in a n-1-dimensional subspace of ${\Bbb R}^b$. Thus we can also express KVL using the orthogonality conditon Bv = 0 where B is a b-(n-1) by b matrix. One such matrix B is the fundamental loop matrix and describes a set of b-(n-1) loops in the circuit from which all loops in the circuit can be derived. This is another way to view KVL: the algebraic sum of branch voltages in a loop is 0.
The complete description of the electronic circuit can be given by KVL, KCL, the constituency relations of the elements and the defining equations $i = \frac{dq}{dt}$ and $v = \frac{d\phi}{dt}$. This gives us a set of constrained differential equations which describes the system. It is not always possible to obtain a set of ordinary differential equations. In the case that we can, it will be given in the form
\begin{equation}\label{eqn:state_circuit} \begin{array}{lclr}
\frac{dq}{dt} & =& f_1(q,\phi) & \qquad \mbox{Eq.} (1)\\
\frac{d\phi}{dt} & = & f_2(q,\phi) & \end{array}
\end{equation}
where q is the charge vector corresponding to the charges of all the capacitors and $\phi$ is the flux vector corresponding to the flux of the inductors. The state vector is $(q,\phi)$. In the case where the capacitors and inductors are linear, we have q = Cv and $\phi = Li$, so for $C\neq 0$ and $L\neq 0$, we can also choose $(v,i)$ as the state vector. This is more desirable since voltages and currents can be more easily measured. Furthermore, this change of variables can be also be done if there is a diffeomorphism between q and v and between $\phi$ and i. The system defined by (v,i) is topologically conjugate to Eq. (1) via the diffeomorphism. The number of equations in Eq. (1) will correspond the the total number of capacitors and inductors since we only have 2-terminal capacitors and inductors.
When there are no dynamic elements the circuit is called a resistive circuit and the equations of the circuit are given by Ai=0, Bv = 0 and R(i,v) = 0. This is a set of nonlinear equations, the solutions of which define the operating voltages and currents of the circuit. There is no dynamics in this system. A solution of these equations is an operating point of the circuit and corresponds to the actual voltages and currents we observe in the circuit.
Now a circuit with more than one operating point presents somewhat of a problem. What does the physical circuit choose as the operating point? In practice, the circuit can be at different operating points depending on when or how you power on the system. To resolve this problem we postulate that parasitic capacitances and inductors are present in parallel and series respectively which results in a dynamic circuit. Consider the state equations (Eq. (1)). The equilibrium points correspond to points when $dq/dt = 0$ for the capacitors and $d\phi/dt = 0$ for the inductors. This corresponds to the capacitor currents equal to zero and inductor voltages equal to zero. Thus we can replace capacitors by a open circuit and inductors by a short circuit which results in the original resistive circuit.
Thus the operating points of the resistive circuit corresponds to equilibrium points of the dynamic circuit and initial conditions play a role in what equilibrium point we will see at steady state (assuming that the state trajectory of the dynamic circuit does converge to an equilibrium point) which corresponds to the operating point we observe.
In part 2, we will look at some simple circuits and their corresponding state equations.
[1] L. O. Chua, Introduction to nonlinear network theory, McGraw-Hill, 1969.
[2] L. O. Chua, C. A. Desoer, E. S. Kuh, Linear and nonlinear circuits, McGraw-Hill, 1987.
[3] L. O. Chua, Memristor-The missing circuit element, IEEE Transactions on Circuit Theory, Sept. 1971, vol. 18, no. 5, pp. 507-519.
[4] D. B. Strukov, G. S. Snider, D. R. Stewart1 & R. S. Williams, The missing memristor found, Nature 453, 1 May 2008, pp. 80-83.
Saturday, March 2, 2013
WYSINWYG (What you see is NOT what you get)
The old adage of appearances being deceptive is true on many different levels. More abstractly consider the problem of communicating the properties of an object or of a concept C from point A to point B. There are many reasons why this communication is imperfect. In fact, there could be a problem at every stage of the communication process.
First of all not all of the properties of C are transmitted to B. This could be deliberate, such as in the game poker or the game Mastermind, where after each trial, only the number of in-location matches and out-location matches are revealed, not their positions. Or it could be limitations of the physical world, for instance, we can only see the outside of an object, (i.e. you can not judge a book by its cover).
Secondly, the transmission medium could distort the information. For instance, we don't see as well at a foggy night. In communication theory, noise in the transmission channel can make the information at the receiving end different than at the transmitting end. Typically, information is lost in this process, i.e. it is not possible to recover all the information transmitted from point A from the information received at point B. Or this could be a fundamental consequence of quantum physics, where the act of observation influences the object being observed.
Thirdly, the sensor apparatus used to receive the information can be deficient. Our eyes can only register lights in the visible spectrum, our ears can only hear in the range of approximately 20Hz-20kHz. This means that something that is invisible (or inaudible) to one animal (or machine), may not be to another. For instance, our warm bodies emit infrared light, but we cannot see it in the dark. However, night vision goggles allow us to see in the dark by using an infrared sensor to capture that radiation and convert it into visible signals that we can see. I have always wondered about the invisibility cloak in the Harry Potter novels or the invisibility serum in H.G. Wells' The Invisible Man, whether they work across the entire electromagnetic spectrum. If they only work in the visible light spectrum, then they could be easily defeated with modern technology by using either an infrared light source (a warm object does by itself emit infrared radiation) or ultraviolet light source (a black light) and using an infrared or ultraviolet sensor to "see" the invisible person. In addition, there are other sensor modalities, e.g. sonar which uses (ultra)sound waves or radar which uses electromagnetic radiation at the radio waves range, that need to addressed for such invisibility cloaks to be truly invisible.
First of all not all of the properties of C are transmitted to B. This could be deliberate, such as in the game poker or the game Mastermind, where after each trial, only the number of in-location matches and out-location matches are revealed, not their positions. Or it could be limitations of the physical world, for instance, we can only see the outside of an object, (i.e. you can not judge a book by its cover).
Secondly, the transmission medium could distort the information. For instance, we don't see as well at a foggy night. In communication theory, noise in the transmission channel can make the information at the receiving end different than at the transmitting end. Typically, information is lost in this process, i.e. it is not possible to recover all the information transmitted from point A from the information received at point B. Or this could be a fundamental consequence of quantum physics, where the act of observation influences the object being observed.
Thirdly, the sensor apparatus used to receive the information can be deficient. Our eyes can only register lights in the visible spectrum, our ears can only hear in the range of approximately 20Hz-20kHz. This means that something that is invisible (or inaudible) to one animal (or machine), may not be to another. For instance, our warm bodies emit infrared light, but we cannot see it in the dark. However, night vision goggles allow us to see in the dark by using an infrared sensor to capture that radiation and convert it into visible signals that we can see. I have always wondered about the invisibility cloak in the Harry Potter novels or the invisibility serum in H.G. Wells' The Invisible Man, whether they work across the entire electromagnetic spectrum. If they only work in the visible light spectrum, then they could be easily defeated with modern technology by using either an infrared light source (a warm object does by itself emit infrared radiation) or ultraviolet light source (a black light) and using an infrared or ultraviolet sensor to "see" the invisible person. In addition, there are other sensor modalities, e.g. sonar which uses (ultra)sound waves or radar which uses electromagnetic radiation at the radio waves range, that need to addressed for such invisibility cloaks to be truly invisible.
Subscribe to:
Posts (Atom)