On repeated roots

Following up with the last post, we wanted to understand why $xe^{-2x}$ is the solution when $-2$ is a repeated root.

Let's start with this, $(p(x) e^{ax})^{(k)}$

We notice this pattern

$(p(x)e^{ax})' = e^{ax}(ap(x) + p'(x))$
$(p(x)e^{ax})'' = e^{ax}(a^2p(x) + 2ap'(x) + p''(x))$
$(p(x)e^{ax})''' = e^{ax}(a^3p(x) + 3a^2p'(x) + 3ap''(x) + p'''(x))$

Feel like binomial expansion? Let's prove this.

Let $S(n)$ be the statement $(p(x)e^{ax})^{(n)} = e^{ax}\sum\limits_{i=0}^{n}(\left(\begin{array}{c}n\\i\end{array}\right)a^i p^{(n-i)}(x))$

$S(0)$ is obviously true, now let's assume $S(k)$ is true and

$(p(x)e^{ax})^{(k)} = e^{ax}\sum\limits_{i=0}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k-i)}(x))$

Now we differentiate both sides once more, we get

$(p(x)e^{ax})^{(k+1)} = e^{ax} (\sum\limits_{i=0}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k-i)}(x)))' + ae^{ax}\sum\limits_{i=0}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k-i)}(x))$

Don't be shied away from the first term, it is just differentiating polynomials, so adding 1 to the differentiation times and that's all. grouping terms, we will get

$\begin{eqnarray*} (p(x)e^{ax})^{(k+1)} &=& e^{ax} \sum\limits_{i=0}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k+1-i)}(x)) + ae^{ax}\sum\limits_{i=0}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k-i)}(x)) \\ &=& e^{ax} \sum\limits_{i=0}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k+1-i)}(x)) + ae^{ax}\sum\limits_{i=1}^{k+1}(\left(\begin{array}{c}k\\i - 1\end{array}\right)a^{i-1} p^{(k+1-i)}(x)) \\ &=& e^{ax} \sum\limits_{i=0}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k+1-i)}(x)) + e^{ax}\sum\limits_{i=1}^{k+1}(\left(\begin{array}{c}k\\i - 1\end{array}\right)a^i p^{(k+1-i)}(x)) \\ &=& e^{ax} \left(\begin{array}{c}k\\0\end{array}\right)a^0 p^{(k+1-0)}(x) + e^{ax} \sum\limits_{i=1}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k+1-i)}(x)) + e^{ax}\sum\limits_{i=1}^{k}(\left(\begin{array}{c}k\\i - 1\end{array}\right)a^i p^{(k+1-i)}(x)) + e^{ax}\left(\begin{array}{c}k\\k+1 - 1\end{array}\right)a^{k+1} p^{(k+1-(k+1))}(x) \\ &=& e^{ax} a^0 p^{(k+1)}(x) + e^{ax} \sum\limits_{i=1}^{k}(\left(\begin{array}{c}k\\i\end{array}\right)a^i p^{(k+1-i)}(x)) + e^{ax}\sum\limits_{i=1}^{k}(\left(\begin{array}{c}k\\i - 1\end{array}\right)a^i p^{(k+1-i)}(x)) + e^{ax}a^{k+1} p^{(0)}(x) \\ &=& e^{ax} a^0 p^{(k+1)}(x) + e^{ax} \sum\limits_{i=1}^{k}(\left(\left(\begin{array}{c}k\\i\end{array}\right)+\left(\begin{array}{c}k\\i-1\end{array}\right)\right)a^i p^{(k+1-i)}(x)) + e^{ax}a^{k+1} p^{(0)}(x) \\ &=& e^{ax} a^0 p^{(k+1)}(x) + e^{ax} \sum\limits_{i=1}^{k}(\left(\begin{array}{c}k + 1\\i\end{array}\right)a^i p^{(k+1-i)}(x)) + e^{ax}a^{k+1} p^{(0)}(x) \\ &=& e^{ax} \sum\limits_{i=0}^{k+1}(\left(\begin{array}{c}k + 1\\i\end{array}\right)a^i p^{(k+1-i)}(x)) \\ \end{eqnarray*}$

Well, a little more complicated than I wanted it to be, but I proved the result.

Next, we assume the differential equation has constant coefficient like this $\sum\limits_{j=0}^{n} c_j y^{(j)} = 0$, and that $r$ is a root of multiplicity $k$. In this case, we claim $x^m e^{rx}$ is a solution for the differential equation for $0 \le m < k$. All we need to do is to put it back to the equation and use our result above:

$\begin{eqnarray*} & & \sum\limits_{j=0}^{n} c_j y^{(j)} \\ &=& \sum\limits_{j=0}^{n} c_j e^{rx}\sum\limits_{i=0}^{j}(\left(\begin{array}{c}j\\i\end{array}\right)r^i p^{(j-i)}(x)) \\ &=& e^{rx} \sum\limits_{j=0}^{n} c_j \sum\limits_{i=0}^{j}(\left(\begin{array}{c}j\\i\end{array}\right)r^i p^{(j-i)}(x)) \\ &=& e^{rx} \sum\limits_{j=0}^{n} c_j \sum\limits_{i=0}^{j}(\left(\begin{array}{c}j\\i\end{array}\right)r^{j-i} p^{(i)}(x)) \\ &=& e^{rx} \sum\limits_{i=0}^{n} \sum\limits_{j=i}^{n} c_j (\left(\begin{array}{c}j\\i\end{array}\right)r^{j-i} p^{(i)}(x)) \\ &=& e^{rx} \sum\limits_{i=0}^{n} \sum\limits_{j=i}^{n} c_j (\frac{j!}{i! (j-i)!}r^{j-i} p^{(i)}(x)) \\ &=& e^{rx} \sum\limits_{i=0}^{n} \frac{p^{(i)}(x)}{i!} \sum\limits_{j=i}^{n} c_j (\frac{j!}{(j-i)!}r^{j-i} ) \\ \end{eqnarray*}$

Note that the inner summation is really just the characteristics polynomial differentiated $i$ times evaluated at $r$, and we know $r$ is a root of multiplicity $k$, so for all $i < k$, the term is zero.

For the other terms, we differentiated $p(x)$ at least $k$ times, but $p(x) = x^m$, so the derivative vanishes, and those terms go to 0 as well. Combining the two facts, the differential equation is satisfied, and therefore it is a solution!

Q.E.D.

The magic step of the fourth equal sign probably need some explanation. One can better visualize that if one programs, it is basically a loop transformation

for (j = 0 to n) { for (i = 0 to j } { } }

is transformed to

for (i = 0 to n) { for (j = i to n } { } }

The easiest way to see why this transformation is valid is by generating the (i, j) tuples created by these loops.

Second order constant coefficients (I)

Problem:

$y'' + 4y' + 4y = 0$

Solution:

Note that we do not have the independent variable $x$, in principle we could have reduce to order to 1, but for this one let's try the solution $y = e^{rx}$. Putting the solution in the problem, we have

$r^2e^{rx} + 4re^{rx} + 4e^{rx} = 0$

Solving, get $r = -2$ (repeated).

The repeated solution worried me because then we have only one degree of freedom.

Let's try $y = xe^{rx}$, $y' = e^{rx} + rxe^{rx}$, $y'' = re^{rx} + re^{rx} + r^2xe^{rx}$

$y'' + 4y' + 4y = (re^{rx} + re^{rx} + r^2xe^{rx}) + 4(e^{rx} + rxe^{rx}) + 4(xe^{rx})$
$= e^{rx}((r + r + r^2x) + 4(1 + rx) + 4(x))$
$= e^{rx}(2r + 4+ (r^2 + 4r + 4))$

So if we put $r = -2$, the equation still work out, so the solution is

$Ae^{-2x} + Bxe^{-2x}$.

To be honest, I kind of know $xe^{-2x}$ is an answer when I see the double root. I know it because of my experience (sort of my teacher told me so thing). But wouldn't it be more satisfying if we figured out the general rule and why the general rule work? Let's investigate in the next post.

Reduction of order (II)

Problem:

$y'' - y'y = 0$

Solution:

This time we see $x$ does not appear in the equation, we can let $z = y'$ and $y'' = \frac{dz}{dx} = \frac{dz}{dy}\frac{dy}{dx} = z'z$, note that $z'$ denote $\frac{dz}{dy}$.

The equation becomes

$\begin{eqnarray*} y'' - y'y &=& 0 \\ z'z - z y &=& 0 \\ z'z &=& z y \\ z' &=& y \\ z &=& \frac{y^2}{2} + c_1 \\ y' &=& \frac{y^2}{2} + c_1 \\ \frac{2dy}{y^2 + c_2^2} &=& dx \\ 2 \arctan(y/c_2)/c_2 &=& x + c_3 \\ \arctan(y/c_2) &=& \frac{c_2x + c_4}{2} \\ y/c_2 &=& \tan\frac{c_2x + c_4}{2} \\ y &=& c_2 \tan\frac{c_2x + c_4}{2} \\ y &=& 2 c_5 \tan(c_5x + c_6) \\ \end{eqnarray*}$

Check:

$\begin{eqnarray*} y &=& 2 c_5 \tan(c_5x + c_6) \\ y' &=& 2 c_5 \sec^2(c_5x + c_6) (c_5) \\ &=& 2 c_5^2 \sec^2(c_5x + c_6) \\ y'' &=& 2 c_5^2 (2 \sec(c_5x + c_6))(\sec(c_5x + c_6) \tan(c_5x + c_6)) (c_5) \\ &=& 4 c_5^3 \sec^2(c_5x + c_6) \tan(c_5x + c_6) \end{eqnarray*}$

Reduction of order (I)

Problem:

$y'' - y' = x$

Solution:

y is missing from the equation, so we can simply let $z = y'$ and so $y'' = z'$. The equation is reduced to

$\frac{dz}{dx} - z = x$

This is a first order linear equation, by inspection, the integrating factor is $e^{-x}$, we have

$\frac{d}{dx}(e^{-x} z) = e^{-x} \frac{dz}{dx} - e^{-x} z = e^{-x} (\frac{dz}{dx} - z) = x e^{-x}$.

Therefore $e^{-x} z = \int {x e^{-x} dx } = - xe^{-x} - e^{-x} + C_1$.

Then we have $z = -x - 1 + C_1e^x$

Last but not least, $y = \int z dx = -\frac{x^2}{2} - x + C_1e^x + C_2$.

Logic Riddle

Problem:

Solution:

If it is in box 1, then message 1 is false, message 2 is true, message 3 is false. [Good!]
If it is in box 2, then message 1 is true, message 2 is false, message 3 is true. [Bad!]
If it is in box 3, then message 1 is true, message 2 is true, message 3 is false. [Bad!]

So it is in box1!

Integrating Factor

Problem:

$\frac{2y}{x^2}dx + \frac{1}{x}dy = 0$.

Solution:

Let $M(x, y) = \frac{2y}{x^2}$, $N(x, y) = \frac{1}{x}$, now we have

$\frac{\partial M}{\partial y} = \frac{2}{x^2} \ne \frac{-1}{x^2} = \frac{\partial N}{\partial x}$

But they look similar, so let's assume there exists $\mu(x)$ such that

$\frac{\partial \mu M}{\partial y} = \frac{\mu \partial N}{\partial x}$

Expanding, we get

$\mu \frac{\partial M}{\partial y} = \frac{\partial \mu}{\partial x} N + \mu \frac{\partial N}{\partial x}$

or

$\frac{1}{N}(\frac{\partial M}{\partial y} - \frac{\partial N}{\partial x})= \frac{1}{\mu}\frac{\partial \mu}{\partial x}$

so

$\mu = e^{\int \frac{1}{N}(\frac{\partial M}{\partial y} - \frac{\partial N}{\partial x}) dx}$

Putting in the values, we have

$\begin{eqnarray*} \mu &=& e^{\int \frac{1}{\frac{1}{x}}(\frac{2}{x^2} - \frac{-1}{x^2}) dx} \\ &=& e^{\int \frac{1}{\frac{3}{x}} dx} \\ &=& e^{3 \log x} \\ &=& x^3 \end{eqnarray*}$

The rest is rather easy now, we need to find $f(x, y)$ such that $\frac{\partial f}{\partial x} = x^3 \frac{2y}{x^2} = 2xy$ and $\frac{\partial f}{\partial y} = x^3 \frac{1}{x} = x^2$. We found $f(x, y) = x^2y = c$, therefore the solution to the differential equation is $y = cx^{-2}$.

Homogenous Equation

Problem:

$(y^2 - x^2)dx + xydy = 0$

Solution:

$\begin{eqnarray*} (y^2 - x^2)dx + xydy &=& 0 \\ (y^2 - x^2)dx &=& -xydy \\ \frac{dy}{dx} &=& \frac{x^2 - y^2}{xy} \\ &=& \frac{x}{y} - \frac{y}{x} \\ \end{eqnarray*}$

Now let $z = \frac{y}{x}, \frac{dz}{dx} = \frac{d}{dx}(y)\frac{1}{x} + y\frac{d}{dx}\frac{1}{x} = \frac{dy}{dx}\frac{1}{x} - \frac{y}{x^2}$, which implies $\frac{dy}{dx} = x\frac{dz}{dx} + z$. Putting these back, we have

$\begin{eqnarray*} \frac{dy}{dx} &=& \frac{x}{y} - \frac{y}{x} \\ x\frac{dz}{dx} + z &=& \frac{1}{z} - z \\ x\frac{dz}{dx} &=& \frac{1}{z} - 2z \\ \frac{zdz}{1-2z^2} &=& \frac{dx}{x} \\ \frac{-1}{4}\log(1-2z^2) &=& \log(x) + C_1 \\ \log(1-2z^2) &=& -4\log(x) + C_2 \\ 1-2z^2 &=& C_3x^{-4} \\ 1-2(\frac{y}{x})^2 &=& C_3x^{-4} \\ x^2-2y^2 &=& C_3x^{-2} \\ y^2 &=& \frac{1}{2}(x^2 - Cx^{-2}) \\ \end{eqnarray*}$

For a quick check, we have:

$\begin{eqnarray*} y^2 &=& \frac{1}{2}(x^2 - Cx^{-2}) \\ 2y \frac{dy}{dx} &=& x + Cx^{-3} \\ &=& x + \frac{Cx^{-2}}{x} \\ &=& x + \frac{x^2 - 2y^2}{x} \\ &=& 2x - \frac{2y^2}{x} \\ \frac{dy}{dx} &=& \frac{x}{y} - \frac{y}{x} \\ \end{eqnarray*}$

Orthogonal Trajectories

Problem:

Find the orthogonal trajectories to the curves $y = x^2 + c$.

Solution:

First, we express the parabolas as differential equations

$\frac{dy}{dx} = 2x$

Next, the slope of the tangent lines for the orthogonal trajectories is determined, so we solve this

$\frac{dy}{dx} = \frac{-1}{2x}$

This is separable, and therefore the solution is simply

$y = \frac{-1}{2}sgn(x)\ln|x| + c$

Exact differential equation

Problem:

$3x^2y dx + x^3dy = 0$

Solution:

We have $\frac{\partial 3x^2y}{\partial y} = 3x^2 = \frac{\partial x^3}{\partial x}$, therefore, we can find $f(x, y)$ such that $\frac{\partial f}{\partial x} = 3x^2y$ and $\frac{\partial f}{\partial y} = x^3$

It is quite obvious that $f(x, y) = x^3y + c$.

The answer to the differential equation is therefore $y = cx^{-3}$.

As a quick check, we have $\frac{dy}{dx} = -3cx^{-4}$, therefore

$3x^2y dx + x^3dy = 3x^2(cx^{-3})dx + x^3(-3cx^{-4})dx = 0$.

First order linear differential equation

Problem:

$y' + 2xy = x$

Solution:

This is a first order linear differential equation, let's consider the derivative of the following form:

$(p(x)e^{q(x)})' = p'(x)e^{q(x)} + p(x)q'(x)e^{q(x)} = e^{q(x)}(p'(x) + p(x)q'(x))$

Now we set $p(x) = y$, $q'(x) = 2x$, we can multiply both side by $e^{x^2}$ to get

$\begin{eqnarray*} e^{x^2}(y' + 2xy) &=& xe^{x^2} \\ (e^{x^2}y)' &=& xe^{x^2} \\ (e^{x^2}y) &=& \int{xe^{x^2}dx} \\ &=& \frac{1}{2}\int{e^{x^2}d(x^2)} \\ &=& \frac{1}{2}e^{x^2} + C \\ y &=& \frac{1}{2} + Ce^{x^{-2}} \\ \end{eqnarray*}$

Definite Integrals using Complex Residue (2)

Problem:

For $b^2 < 4ac$: $\int\limits_{-\infty}^{+\infty}{\frac{dx}{(ax^2+bx+c)^2}}$

Solution:

Consider the contour concatenating $-R$ to $R$ and then go through a half circle in the upper half plane back to $-R$, the half circle part goes to 0 (*), so all we need to do is to compute the residue in the upper half plane.

The integrand can be factorized as:

$\begin{eqnarray*} & & \frac{1}{(ax^2 + bx + c)^2} \\ &=& \frac{1}{(\frac{1}{4a}(2ax + b + \sqrt{b^2 - 4ac})(2ax + b - \sqrt{b^2 - 4ac}))^2} \\ &=& \frac{16a^2}{(2ax + b + \sqrt{b^2 - 4ac})^2(2ax + b - \sqrt{b^2 - 4ac})^2} \\ \end{eqnarray*}$

So we have two poles with order 2: $x = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$ and $x = \frac{-b - \sqrt{b^2 - 4ac}}{2a}$, only the first pole is in the upper half plane, so we compute the residue there.

$\begin{eqnarray*} & & Res[\frac{16a^2}{(2ax + b + \sqrt{b^2 - 4ac})^2(2ax + b - \sqrt{b^2 - 4ac})^2}, \frac{-b + \sqrt{b^2 - 4ac}}{2a}] \\ &=& \lim\limits_{x \to \frac{-b + \sqrt{b^2 - 4ac}}{2a}}{((x - \frac{-b + \sqrt{b^2 - 4ac}}{2a})^2\frac{16a^2}{(2ax + b + \sqrt{b^2 - 4ac})^2(2ax + b - \sqrt{b^2 - 4ac})^2})'} \\ &=& \lim\limits_{x \to \frac{-b + \sqrt{b^2 - 4ac}}{2a}}{((\frac{2ax + b - \sqrt{b^2 - 4ac}}{2a})^2\frac{16a^2}{(2ax + b + \sqrt{b^2 - 4ac})^2(2ax + b - \sqrt{b^2 - 4ac})^2})'} \\ &=& \lim\limits_{x \to \frac{-b + \sqrt{b^2 - 4ac}}{2a}}{(\frac{4}{(2ax + b + \sqrt{b^2 - 4ac})^2})'} \\ &=& \lim\limits_{x \to \frac{-b + \sqrt{b^2 - 4ac}}{2a}}{(\frac{(-2)4}{(2ax + b + \sqrt{b^2 - 4ac})^3})(2a)} \\ &=& \lim\limits_{x \to \frac{-b + \sqrt{b^2 - 4ac}}{2a}}{\frac{-16a}{(2ax + b + \sqrt{b^2 - 4ac})^3}} \\ &=& \frac{-16a}{(2a(\frac{-b + \sqrt{b^2 - 4ac}}{2a}) + b + \sqrt{b^2 - 4ac})^3} \\ &=& \frac{-16a}{((-b + \sqrt{b^2 - 4ac}) + b + \sqrt{b^2 - 4ac})^3} \\ &=& \frac{-16a}{(2\sqrt{b^2 - 4ac})^3} \\ &=& \frac{-2a}{(\sqrt{b^2 - 4ac})^3} \\ \end{eqnarray*}$

Going back to the integral, we get:

$\begin{eqnarray*} & & \int\limits_{-\infty}^{+\infty}{\frac{dx}{(ax^2+bx+c)^2}} \\ &=& 2\pi i \frac{-2a}{(\sqrt{b^2 - 4ac})^3} \\ &=& \frac{-4\pi a i}{(\sqrt{b^2 - 4ac})^3} \\ &=& \frac{4\pi a}{(\sqrt{4ac - b^2})^3} \\ \end{eqnarray*}$

Definite Integrals using Complex Residue (1)

Problem:

$\int\limits_{-\pi}^{\pi}{\frac{\cos\theta}{a + b \cos\theta}d\theta}$

Solution:

This exercise use the substitution $z = e^{i\theta}$.
That led to $dz = ie^{i\theta}d\theta$, and therefore $\frac{dz}{iz} = d\theta$.
The integration limit becomes a unit circle.

Using the Euler's identity $\cos \theta + i\sin\theta = e^{i\theta} = z$, we can write trigonometric functions in terms of $z$

$\cos \theta = \frac{e^{i\theta} + e^{-i\theta}}{2} = \frac{z + \frac{1}{z}}{2}$.
$\sin \theta = \frac{e^{i\theta} - e^{-i\theta}}{2i} = \frac{z - \frac{1}{z}}{2i}$.

Here is one more convenient result for factorizing general quadratic equation:

$\begin{eqnarray*} & & ax^2 + bx + c \\ &=& \frac{1}{4a}(4ax^2 + 4abx + 4ac) \\ &=& \frac{1}{4a}((2ax)^2 + 4abx + 4ac) \\ &=& \frac{1}{4a}((2ax)^2 + 4abx + b^2 - b^2 + 4ac) \\ &=& \frac{1}{4a}((2ax + b)^2 - b^2 + 4ac) \\ &=& \frac{1}{4a}((2ax + b)^2 - (b^2 - 4ac)) \\ &=& \frac{1}{4a}((2ax + b)^2 - (\Delta)^2) \\ &=& \frac{1}{4a}((2ax + b + \Delta)(2ax + b - \Delta)) \end{eqnarray*}$

Now, we are all set to start solving the problems.


$\begin{eqnarray*} & & \int\limits_{-\pi}^{\pi}{\frac{\cos\theta}{a + b \cos\theta}d\theta} \\ &=& \oint{\frac{\frac{z + \frac{1}{z}}{2}}{a + b \frac{z + \frac{1}{z}}{2}}\frac{dz}{iz}} \\ &=& \oint{\frac{z + \frac{1}{z}}{2a + b (z + \frac{1}{z})}\frac{dz}{iz}} \\ &=& \oint{\frac{z^2 + 1}{2az + b (z^2 + 1)}\frac{dz}{iz}} \\ &=& \oint{\frac{z^2 + 1}{bz^2 + 2az + b}\frac{dz}{iz}} \\ \end{eqnarray*}$

To move on, we factorize the quadratic expression, computing $\Delta$.

$\begin{eqnarray*} \Delta &=& \sqrt{(2a)^2 - 4(b)(b)} \\ &=& 2 \sqrt{a^2 - b^2} \end{eqnarray*}$

So we move on

$\begin{eqnarray*} & & \int\limits_{-\pi}^{\pi}{\frac{\cos\theta}{a + b \cos\theta}d\theta} \\ &=& \oint{\frac{z^2 + 1}{\frac{1}{4b}(2bz + 2a + 2 \sqrt{a^2 - b^2})(2bz + 2a - 2 \sqrt{a^2 - b^2})}\frac{dz}{iz}} \\ &=& \oint{\frac{z^2 + 1}{\frac{1}{b}(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{dz}{iz}} \\ &=& \oint{\frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{dz}{iz}} \\ \end{eqnarray*}$

We have three poles with 1st order: $z = 0$, $z = -\frac{a + \sqrt{a^2 - b^2}}{b}$ and $z = \frac{\sqrt{a^2 - b^2} - a}{b}$ Only the first and last is within the unit circle.

Next, we compute the residue values using limits

$\begin{eqnarray*} & & Res[\frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{1}{iz}, 0] \\ &=& \lim\limits_{z \to 0}(z \frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{1}{iz}) \\ &=& \lim\limits_{z \to 0}(\frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{1}{i}) \\ &=& \frac{b((0)^2 + 1)}{(b(0) + a + \sqrt{a^2 - b^2})(b(0) + a - \sqrt{a^2 - b^2})}\frac{1}{i} \\ &=& \frac{b}{(a + \sqrt{a^2 - b^2})(a - \sqrt{a^2 - b^2})}\frac{1}{i} \\ &=& \frac{b}{(a^2 - (a^2 - b^2))}\frac{1}{i} \\ &=& \frac{b}{b^2}\frac{1}{i} \\ &=& \frac{1}{b}\frac{1}{i} \\ \end{eqnarray*}$

We also have

$\begin{eqnarray*} & & Res[\frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{1}{iz}, \frac{\sqrt{a^2 - b^2} - a}{b}] \\ &=& \lim\limits_{z \to \frac{\sqrt{a^2 - b^2} - a}{b}}((z - \frac{\sqrt{a^2 - b^2} - a}{b}) \frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{1}{iz}) \\ &=& \lim\limits_{z \to \frac{\sqrt{a^2 - b^2} - a}{b}}(\frac{1}{b}(bz - (\sqrt{a^2 - b^2} - a)) \frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{1}{iz}) \\ &=& \lim\limits_{z \to \frac{\sqrt{a^2 - b^2} - a}{b}}(\frac{1}{b}(bz + a - \sqrt{a^2 - b^2}) \frac{b(z^2 + 1)}{(bz + a + \sqrt{a^2 - b^2})(bz + a - \sqrt{a^2 - b^2})}\frac{1}{iz}) \\ &=& \lim\limits_{z \to \frac{\sqrt{a^2 - b^2} - a}{b}}(\frac{1}{b} \frac{b(z^2 + 1)}{bz + a + \sqrt{a^2 - b^2}}\frac{1}{iz}) \\ &=& \frac{1}{b} \frac{b((\frac{\sqrt{a^2 - b^2} - a}{b})^2 + 1)}{b(\frac{\sqrt{a^2 - b^2} - a}{b}) + a + \sqrt{a^2 - b^2}}\frac{1}{i(\frac{\sqrt{a^2 - b^2} - a}{b})} \\ &=& \frac{1}{b} \frac{b((\frac{\sqrt{a^2 - b^2} - a}{b})^2 + 1)}{\sqrt{a^2 - b^2} - a + a + \sqrt{a^2 - b^2}}\frac{1}{i(\frac{\sqrt{a^2 - b^2} - a}{b})} \\ &=& \frac{1}{b} \frac{b((\frac{\sqrt{a^2 - b^2} - a}{b})^2 + 1)}{2\sqrt{a^2 - b^2}}\frac{1}{i(\frac{\sqrt{a^2 - b^2} - a}{b})} \\ &=& \frac{1}{b} \frac{b^2((\frac{\sqrt{a^2 - b^2} - a}{b})^2 + 1)}{2\sqrt{a^2 - b^2}}\frac{1}{i(\sqrt{a^2 - b^2} - a)} \\ &=& \frac{1}{b} \frac{(\sqrt{a^2 - b^2} - a)^2 + b^2}{2\sqrt{a^2 - b^2}}\frac{1}{i(\sqrt{a^2 - b^2} - a)} \\ &=& \frac{1}{b} \frac{(a^2 - b^2) - 2a\sqrt{a^2 - b^2} + a^2 + b^2}{2\sqrt{a^2 - b^2}}\frac{1}{i(\sqrt{a^2 - b^2} - a)} \\ &=& \frac{1}{b} \frac{2a^2 - 2a\sqrt{a^2 - b^2}}{2\sqrt{a^2 - b^2}}\frac{1}{i(\sqrt{a^2 - b^2} - a)} \\ &=& \frac{1}{b} \frac{-2a(\sqrt{a^2 - b^2} - a)}{2\sqrt{a^2 - b^2}}\frac{1}{i(\sqrt{a^2 - b^2} - a)} \\ &=& \frac{1}{b} \frac{-a}{\sqrt{a^2 - b^2}}\frac{1}{i} \\ \end{eqnarray*}$

Last, we put these back to the integral, we have

$\begin{eqnarray*} & & \int\limits_{-\pi}^{\pi}{\frac{\cos\theta}{a + b \cos\theta}d\theta} \\ &=& 2\pi i(\frac{1}{b}\frac{1}{i} + \frac{1}{b} \frac{-a}{\sqrt{a^2 - b^2}}\frac{1}{i}) \\ &=& \frac{2\pi}{b} (1 - \frac{a}{\sqrt{a^2 - b^2}}) \\ \end{eqnarray*}$

Q.E.D. This took me 1.5 hours.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 11

Problem:

Solution:

Part (a) is trivial given exercise 8, we already know to parametrization of the curve $y^2 = cx^2 - x^3$, just replace $(x, y)$ by $(z ,x)$ we get what we want.

For part (b) is just as simple, we replace $y$ by $u$ and set $c = y^2 = u^2$, then we are done.

For any point on the surface, $y$ must be either positive, 0 or negative. In any case, we reduce to a particular curve $x^2 = cz^2 - z^3$, now we know by problem 8 part (c) that the parametization covers the whole curve, so the parameterization cover all points on the surface!

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 10

Problem:

Solution:

Wow! What a long question! Okay, warning, long solution ahead.

For part (a), we have done with the trick a lot of times, just use the line through $(a, 0)$. The line is $y = t(a - x)$ (for algebraic simplicity I pick this instead of $y = t(x - a)$). Putting this back to the equation we get


$\begin{eqnarray*} y^2(a + x) &=& (a - x)^3 \\ (t(a - x))^2(a + x) &=& (a - x)^3 \\ t^2(a + x) &=& (a - x) \\ (1 + t^2)x &=& a(1 - t^2) \\ x &=& a\frac{1 - t^2}{1 + t^2} \\ y &=& t(a - x) \\ &=& t(a - a\frac{1 - t^2}{1 + t^2}) \\ &=& ta(1 - \frac{1 - t^2}{1 + t^2}) \\ &=& ta(\frac{1 + t^2}{1 + t^2} - \frac{1 - t^2}{1 + t^2}) \\ &=& ta(\frac{2t^2}{1 + t^2}) \end{eqnarray*}$

It looks like t - substitution again? Indeed, again, there is a relation, see my another earlier post to find that out!

For part (b), the key is to use congruent triangles as in the diagram shown

It is now obvious to see that $\triangle JLP \cong \triangle QGB$, as we already know the x coordinate of $Q$ is simply $x$, the key is to find the y coordinate of $Q$ and this is same as the length as $JL$.

To find $JL$, we use $\triangle JCB \sim \triangle PEB$, we know $\frac{|PE|}{|EB|} = \frac{|JC|}{|CB|}$, so we have

$\begin{eqnarray*} |JL| &=& |JC| - |CL| \\ &=& |JC| - |PE| \\ &=& \frac{|PE| \times |CB|}{|EB|} - |PE| \\ &=& \frac{\sqrt{a^2 - x^2} \times 2a}{a + x} - \sqrt{a^2 - x^2} \\ &=& \frac{\sqrt{a^2 - x^2} \times 2a}{a + x} - \frac{(a + x)\sqrt{a^2 - x^2}}{a+x} \\ &=& \frac{\sqrt{a^2 - x^2} \times (a - x)}{a + x} \\ \end{eqnarray*}$

Now we have found the coordinate $Q$, next we simply substitute that into the equation and prove that it is indeed on the cissoid.
$\begin{eqnarray*} & & y^2(a + x) \\ &=& \left(\frac{\sqrt{a^2 - x^2} \times (a - x)}{a + x}\right)^2(a + x) \\ &=& \frac{(a^2 - x^2) \times (a - x)^2}{(a + x)^2}(a + x) \\ &=& \frac{(a + x)(a - x) \times (a - x)^2}{(a + x)^2}(a + x) \\ &=& (a - x)^3 \\ \end{eqnarray*}$

So the point $Q$ indeed lie on the cissoid.

For part (c), we use two point form to compute the prescribed line as $\frac{y - 0}{x - a} = \frac{\frac{a}{2} - 0}{0 + a}$ which simplifies to $x = 2y - a$.

Now we substitute this into the first x of the cissoid formula, we get

$y^2(2y - a + a) = (x - a)^3$ which readily simplify to $2 = \left(\frac{x - a}{y}\right)^3$.

Phew, what a long question!

A signal processing exercise

Problem:

We are working on the problem 3 of this picture.

Solution:

For part (a), generating a realization of the random process is simple enough.

Let's do a simple review on white noise. A noise is white if its power spectrum is flat. The power spectrum is the Fourier transform of the autocorrelation function. Note that the term 'autocorrelation function' make sense only when we are talking about wide sense stationary signal.

The fact that the power spectrum is flat implies the autocorrelation function is a delta function, which in turns simply implies the samples are uncorrelated.

Therefore, in order to generate the Gaussian white noise, we simply generate a sequence of uncorrelated Gaussian random variables.

To generate $x[n]$, we simply generate $w[n]$ and then run the recursion.

For part (b), we will use the Yule Walker's equation.

The key to the derivation of the Yule Walker's equation is to massage the defining equation to use autocorrelation function, how, just multiply $x[k]$ on both side and take expectation.

For Matlab, this is easily done with a single call to aryule function. Loved Matlab for that.

For part (c), we interpret the autoregressive random process as an Infinite Impulse Response filter on Gaussian white noise. There is a theorem stating that the power spectrum of the filtered signal is simply the power spectrum of the origina lsignal multiply by the square of the transfer function.

Therefore to determine the power spectrum we simply determine the transfer function.

Using z-transform, we can state the following equation:

$X(z) = a_1z^{-1}X(z) + a_2z^{-1}X(z) + a_3z^{-3}X(z) + W(z)$

Rearranging, we get $H(z) = \frac{X(z)}{W(z)} = \frac{1}{1 - a_1z^{-1} - a_2z^{-1} - a_3z^{-3}}$

To obtain the power spectrum, remember the input power spectrum is flat (in fact, identically equals to 1), so we simply ignore that as multiply 1 gives nothing, and take the square of the expression above and evaluate on the unit circle to give coefficients.

For part (d), Bartlett method simply chop the signal into equal non-overlapping windows and then compute the Fourier transform for each window, average them. The point of doing so is to make sure the statistics converge.

Without further ado, this is all the Matlab source code:

function problem3()
  clear; clc;
  
  % part a) generate the samples for the given AR(3) process
  length = 1000;
  old1 = 0;
  old2 = 0;
  old3 = 0;
  x = zeros(1, length);
  w = randn(1, length);
  a1 = 0.8;
  a2 = -0.5;
  a3 = 0.1;
  b0 = 1;
  for i = 1:length
    x(i) = a1 * old1 + a2 * old2 + a3 * old3 + b0 * w(i);
    old3 = old2;
    old2 = old1;
    old1 = x(i);
  end

  % part b) estimate the parameter of the AR process using yule walker
  % equations
  params = aryule(x, 3);
  a1 = params(1)
  a2 = params(2)
  a3 = params(3)

  % part c) plot the power spectral density based on the estimated
  % parameters  
  samples = 0:99;
  z = exp(-2 * pi * sqrt(-1) * samples / 99);
  
  % the process is interpreted as an IIR filter acted on a white noise
  % this the transfer function of the IIR filter  
  h = 1 ./ (1 - a1 ./ z -  a2 ./z ./z - a3 ./z ./z ./z);
  % the power spectral density is given by the square of the transfer 
  % function times to power spectral density of the white noise, which is 
  % identically 1
  p = h .* conj(h);
  
  % estimate the power spectral density based on the Bartlett's method
  num_segments = 10;
  window_size = length / num_segments;
  periodogram = zeros(1, window_size);  
  for i = 0:(num_segments - 1)
    window = x(1, window_size * i + 1: window_size * i + window_size);
    local_fft = fft(window);
    local_fft_magntitude = local_fft .* conj(local_fft);
    periodogram = periodogram + local_fft_magntitude / window_size / num_segments;
  end
  
  figure
  hold on
  plot(p);
  plot(periodogram)

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 9

Problem:

Solution:

The key identity is $1 + \tan^2(t) = \sec^2 t = \frac{1}{\cos^2 t } = \frac{1}{1 - \sin^2 t}$.

With that, we know $x = a \sin t$ so that $\sin t = \frac{x}{a}$, put it into the $y$ equation to get

$\begin{eqnarray*} y^2 &=& a^2 \tan^2 t (1 + \sin t)^2 \\ &=& a^2 (\sec^2 t - 1) (1 + \sin t)^2 \\ &=& a^2 (\frac{1}{1 - \sin^2 t} - 1) (1 + \sin t)^2 \\ &=& a^2 (\frac{1}{1 - (\frac{x}{a})^2} - 1) (1 + \frac{x}{a})^2 \\ &=& (\frac{1}{1 - (\frac{x}{a})^2} - 1) (a + x)^2 \\ &=& (\frac{a^2}{a^2 - x^2} - 1) (a + x)^2 \\ &=& (\frac{a^2}{a^2 - x^2} - \frac{a^2 - x^2}{a^2 - x^2}) (a + x)^2 \\ &=& \frac{x^2}{a^2 - x^2} (a + x)^2 \end{eqnarray*}$

As the hint specify, we cannot multiply over the denominator because then we will introduce an additional straight line $x = -a$ in the graph. This seems to illustrate a different point. While we miss points when we find rational parametization to a curve, we introduce new points when we force ourselves to represent this as polynomial (or variety), I still do not know if it is possible to represent this curve as a variety instead of a rational function.

For part (b), let's us try the usual trick the consider the point intersected by the line through origin. For easy of manipulation, we start with the sloppy formula:

$\begin{eqnarray*} y^2(a^2 - x^2) &=& x^2(a + x)^2 \\ (tx)^2(a^2 - x^2) &=& x^2(a + x)^2 \\ t^2(a^2 - x^2) &=& (a + x)^2 \\ a^2t^2 - t^2x^2 &=& a^2 + 2ax + x^2 \\ (1 + t^2)x^2 + 2ax + a^2(1 - t^2) &=& 0 \\ \end{eqnarray*}$

In the simplification, we already get rid of the double root $x = 0$, we know the sloppy formula introduced the line $x = -a$ so that is not the right answer, consider the sum of roots $s$:

$\begin{eqnarray*} x &=& s - (-a) \\ &=& \frac{-2a}{1 + t^2} -(-a) \\ &=& a - \frac{2a}{1 + t^2} \\ &=& \frac{a(1+t^2)}{1 + t^2} - \frac{2a}{1 + t^2} \\ &=& a\frac{t^2 - 1}{1 + t^2} \\ y &=& tx \\ &=& at\frac{t^2 - 1}{1 + t^2} \end{eqnarray*}$

The answer feel like t substitution, so maybe there is some relationship there. Apparently, we can use the t-substitution to the defining formula directly, but it is not the same as what we get here, but if we do a phase shift of $\frac{\pi}{2}$, then we can get there:

$\begin{eqnarray*} x &=& a \sin(\theta) \\ &=& -a \cos(\theta + \frac{\pi}{2}) \\ &=& -a \frac{1 - t^2}{1 + t^2} \\ &=& a \frac{t^2 - 1}{1 + t^2} \\ y &=& a \tan \theta (1 + \sin \theta) \\ &=& a \frac{1}{\tan(\theta + \frac{\pi}{2})}(1 - \cos (\theta + \frac{\pi}{2})) \\ &=& a \frac{1}{\frac{2t}{1-t^2}}(1 - \frac{1 - t^2}{1 + t^2}) \\ &=& a \frac{1-t^2}{2t}(1 - \frac{1 - t^2}{1 + t^2}) \\ &=& a \frac{1-t^2}{2t}(\frac{1 + t^2}{1 + t^2} - \frac{1 - t^2}{1 + t^2}) \\ &=& a \frac{1-t^2}{2t}(\frac{-2t^2}{1 + t^2}) \\ &=& at\frac{t^2 - 1}{1 + t^2} \end{eqnarray*}$

So we come to full circle!

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 8

Problem:

Solution:

Part (a) is simple. First of all, notice we have a $y^2$ on the left hand side, so normal polynomial reasoning does not apply. The easiest way to do this problem is geometrically.

The line x = d > c cuts the curve at 0 points
The line x = 0 cuts the curve at one point.
The line x = c > e  > 0 cuts the curve at two points.
The line y = 0.1 (assuming it is still the loop area, depending of course on c) cuts the curve at 3 points.

Part (b) is also simple, I will skip the picture. The line through the origin has formula $y = mx$, so if we substitute this into the formula, we get

$(mx)^2 = cx^2 - x^3$.

Then we divide $x^2$ throughout to get $m^2 = c - x$, that is why we get exactly one other point on the curve because the equation will have exactly one solution.

For part (c), just replace $m$ by $t$ above. If $t^2 = c$, we will get the origin. If $t^2 < c$, we will get positive $x$ and therefore the loop region, otherwise we will get negative $x$ and therefore the tails, so we get the whole curve.

This is somewhat unusual, normally parametrization miss some points, but for this one we covered all, perhaps because we do not have a denominator in this case.

For Part (d), we just need to do a little more algebra, we already know $t^2 = c - x$, so $x = c - t^2$, $y = tx = t(c - t^2)$, that's it!

Probability of enclosing the center

Problem:

Given a square, we sample three points at random uniformly on the sides of the square. What is the probability that triangle defined by that three points enclose the center of the square?

Solution:

Denote the points as $\vec{p_1}, \vec{p_2}, \vec{p_3}$. The center of the square is enclosed by the triangle defined by these three points if and only if the center is on the same side of $\vec{p_2}-\vec{p_1}$, $\vec{p_3}-\vec{p_2}$, $\vec{p_1}-\vec{p_3}$,

Here is the key result, the probability that the center of the square is of the left of $\vec{p_2}-\vec{p_1}$ is exactly $\frac{1}{2}$, this is because for each particular event that led to the center being on the left, there is a mirror event (i.e. when $\vec{p_1}$ and $\vec{p_2}$ are reversed) such that the center being on the right.

With that, we can write out the probability as follow

P(enclose) = P(center on the left of $\vec{p_2}-\vec{p_1}$) $\times$ P(center on the left of $\vec{p_3}-\vec{p_2}$) $\times$ P(center on the left of $\vec{p_1}-\vec{p_3}$) $+$ P(center on the right of $\vec{p_2}-\vec{p_1}$) $\times$ P(center on the right of $\vec{p_3}-\vec{p_2}$) $\times$ P(center on the right of $\vec{p_1}-\vec{p_3}$) = $\frac{1}{4}$

The following simple Monte Carlos simulation proves that I am correct with the value of the probability.

namespace ManagedWorkspace
{
    using System;

    static class Program
    {
        static void Main(string[] args)
        {
            Random random = new Random(0);
            int numerator = 0;
            int denominator = 0;
            for (int i = 0; i < 1000000; i++)
            {
                double x1, y1, x2, y2, x3, y3;
                GeneratePoint(random, out x1, out y1);
                GeneratePoint(random, out x2, out y2);
                GeneratePoint(random, out x3, out y3);
                double cross1 = x1 * y2 - x2 * y1;
                double cross2 = x2 * y3 - x3 * y2;
                double cross3 = x3 * y1 - x1 * y3;
                if ((cross1 > 0 && cross2 > 0 && cross3 > 0) || (cross1 < 0 && cross2 < 0 && cross3 < 0))
                {
                    numerator++;
                }
                denominator++;
            }
            Console.WriteLine(numerator + "/" + denominator);
        }

        private static void GeneratePoint(Random random, out double x1, out double y1)
        {
            int edge = random.Next(4);
            switch (edge)
            {
                case 0:
                    y1 = -1;
                    x1 = random.NextDouble() * 2 - 1;
                    return;
                case 1:
                    x1 = 1;
                    y1 = random.NextDouble() * 2 - 1;
                    return;
                case 2:
                    y1 = 1;
                    x1 = random.NextDouble() * 2 - 1;
                    return;
                case 3:
                    x1 = -1;
                    y1 = random.NextDouble() * 2 - 1;
                    return;    
                default:
                    throw new InvalidOperationException("Should not happen");
            }
        }
    }
}

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 7

Problem:

Solution:

The generalization is pretty obvious, we claim that

$x_j = \frac{2u_j}{(\sum\limits_{i = 1}^{n-1}{u_i^2}) + 1}$ for $j = 1 \cdots n - 1$.

$x_n = \frac{(\sum\limits_{i = 1}^{n-1}{u_i^2}) - 1}{(\sum\limits_{i = 1}^{n-1}{u_i^2}) + 1}$ for $j = n$.

All we need to do is to prove that it is correct by substitute that into the equation $x_1^2 + \cdots + x_n^2$ and show that it is identically 1.

$\begin{eqnarray*} & & x_1^2 + \cdots + x_n^2 \\ &=& (\sum\limits_{j = 1}^{n-1}{x_j^2}) + x_n^2 \\ &=& \left(\sum\limits_{j = 1}^{n-1}{\left(\frac{2u_j}{(\sum\limits_{i = 1}^{n-1}{u_i^2}) + 1}\right)^2}\right) + \left(\frac{(\sum\limits_{i = 1}^{n-1}{u_i^2}) - 1}{(\sum\limits_{i = 1}^{n-1}{u_i^2}) + 1}\right)^2 \\ \end{eqnarray*}$

To make our notation simpler, let $S = \sum\limits_{i = 1}^{n-1}{u_i^2}$, so we can simplify to

$\begin{eqnarray*} &=& \left(\sum\limits_{j = 1}^{n-1}{\left(\frac{2u_j}{S + 1}\right)^2}\right) + \left(\frac{S - 1}{S + 1}\right)^2 \\ &=& \frac{1}{(S+1)^2}(\sum\limits_{j = 1}^{n-1}{(2u_j)^2} + (S - 1)^2) \\ &=& \frac{1}{(S+1)^2}(4S + (S - 1)^2) \\ &=& \frac{1}{(S+1)^2}(4S + S^2 - 2S + 1) \\ &=& \frac{1}{(S+1)^2}(S^2 + 2S + 1) \\ &=& \frac{1}{(S+1)^2}(S + 1)^2 \\ &=& 1 \end{eqnarray*}$

An abstract algebra problem

Problem:

Solution:

For part (a), we simply verify all the group axioms:

Closure: For any two matrices $2 \times 2$ with determinant 1, their product must also be a $2 \times 2$ matrix with determinant 1, so closure is satisfied.

Identity: we designate $\left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right)$ be the identity of the group, apparently, it is an element of the group and any matrix multiplied with it must stay the same, so identity is satisfied.

Associative: Associativity of this group simply follows from matrix multiplication.

Inverse: $\left(\begin{array}{cc} a & b \\ c & d \end{array}\right)\left(\begin{array}{cc} d & -b \\ -c & a \end{array}\right) = \left(\begin{array}{cc} ad-bc & -ab+ab \\ cd-cd & -bc+ad \end{array}\right) = \left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right)$, therefore inverse is satisfied.

We will prove part (b) and part (c) together by considering the mapping

$\left(\begin{array}{cc} a & b \\ c & d \end{array}\right) \to \left(\begin{array}{cc} a \mod 2 & b \mod 2 \\ c \mod 2 & d \mod 2 \end{array}\right)$.

It is routine to check this is a homomorphism, the kernel for this mapping are matrices with $a, d$ odd and $b, c$ even and $ad - bc = 1$, therefore it is a normal subgroup (as all kernels are), its image is $SL(2, \mathbf{F_2})$, therefore the quoient group is isomorphic to it.

part (d) is an interesting part, I owe this solution to Raymond Chow.

Consider the elements of  $SL(2, \mathbf{F_2})$ as invertible linear transformations $\mathbf{F_2}^2$, there are four points in  the space, because the mapping is linear, it must map $(0, 0)$ to $(0, 0)$. Because the mapping is invertible, it can only permute the points, so we can build an homomorphism from $SL(2, \mathbf{F_2})$ to $S_3$. Now it is routine to just enumerate the elements and show it is an isomorphism.

It would be really tedious to just write out all of them, for example, here is the computation of one of the matrix

$\left(\begin{array}{cc} 1 & 0 \\ 1 & 1\end{array}\right)\left(\begin{array}{c} 0 \\ 1\end{array}\right) = \left(\begin{array}{c} 0 \\ 1\end{array}\right)$

$\left(\begin{array}{cc} 1 & 0 \\ 1 & 1\end{array}\right)\left(\begin{array}{c} 1 \\ 0\end{array}\right) = \left(\begin{array}{c} 1 \\ 1\end{array}\right)$

$\left(\begin{array}{cc} 1 & 0 \\ 1 & 1\end{array}\right)\left(\begin{array}{c} 1 \\ 1\end{array}\right) = \left(\begin{array}{c} 1 \\ 0\end{array}\right)$

The computation indicate we should map $\left(\begin{array}{cc} 1 & 0 \\ 1 & 1\end{array}\right)$ to $(1, 3, 2)$.

The final mapping is

$\left(\begin{array}{cc} 1 & 0 \\ 0 & 1\end{array}\right) \to (1, 2, 3)$

$\left(\begin{array}{cc} 1 & 0 \\ 1 & 1\end{array}\right) \to (1, 3, 2)$

$\left(\begin{array}{cc} 0 & 1 \\ 1 & 0\end{array}\right) \to (2, 1, 3)$

$\left(\begin{array}{cc} 1 & 1 \\ 1 & 0\end{array}\right) \to (2, 3, 1)$

$\left(\begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right) \to (3, 1, 2)$

$\left(\begin{array}{cc} 1 & 1 \\ 0 & 1\end{array}\right) \to (3, 2, 1)$

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 6

Problem:

Solution:

Part a is the most challenging part of the problem, see the drawing below:

The radius of the circle is 1. Therefore, $|BE| = 2$, the diameter.

By geometry, we know $\measuredangle BDE = 90^{\circ}$ because it is the angle subtended by a semicircle, so we know $\triangle BEC \sim \triangle EDC \sim \triangle EFD$, our goal is to express $|DF|$ and $|EF|$ in terms of $|CE|$.

Once we have the triangle similarity relation, the rest is really just algebra, we know

$\frac{2}{|CE|} = \frac{|BE|}{|CE|} = \frac{|DE|}{|CD|}$ by $\triangle BEC \sim \triangle EDC$, and so $|CD| = \frac{|DE||CE|}{2}$

We also have $|DE|^2 + |CD|^2 = |CE|^2$ by Pythagorean theorem, if we substitute the previous result, then we get $|DE|^2 + (\frac{|DE||CE|}{2})^2 = |CE|^2$, simplifying, we get $4|DE|^2 + |DE|^2 |CE|^2 = 4|CE|^2$, or simply $|DE|^2 = \frac{4|CE|^2}{|CE|^2 + 4}$.

Next, we use another geometry idea that triangle area is the same no matter how it is calculated, in particular, we know $|CD||DE| = |CE||DF|$, we eliminate $|CD|$ by using the similarity relation again, $|DF| = |DE|\frac{|CD|}{|CE|} = |DE|\frac{|DE|}{2} = \frac{|DE|^2}{2} = \frac{2|CE|^2}{|CE|^2 + 4}$

To finish up our story of finding lengths, $|EF|$ can be found by similarity relation as well. $\frac{EF}{DF} = \frac{2}{|CE|}$, therefore we get $|EF| = \frac{2|DF|}{|CE|} = \frac{4|CE|}{|CE|^2 + 4}$

Now, let's relate these geometric results with the parametization problem. Consider this is a cross section view of the sphere with the plane containing the north pole, the origin and the point $(u, v, 0)$. Note that the point $(u, v, 0)$ is on the $z = 0$ plane which is the same as the center, therefore $|CE| = 2\sqrt{u^2 + v^2}$.

Substitute these back to the lengths, we get :

$|DF| = \frac{2|CE|^2}{|CE|^2 + 4} = \frac{2 \times 4(u^2 + v^2)}{4(u^2 + v^2) + 4} = \frac{2u^2 + 2v^2}{u^2 + v^2 + 1}$

$|EF| = \frac{4|CE|}{|CE|^2 + 4} = \frac{4 \times 2\sqrt{u^2 + v^2}}{4(u^2 + v^2) + 4} = \frac{2\sqrt{u^2 + v^2}}{u^2 + v^2 + 1}$

Note the similarity of the formula with the given parametization! To finish the story, we note that by a simply coordinate transformation, $-1 + |EF| = z$, so $z = \frac{2u^2 + 2v^2}{u^2 + v^2 + 1} - 1 = \frac{u^2 + v^2 - 1}{u^2 + v^2 + 1}$.

$x$ and $y$ are slightly more complicated, we know the radial distance of the projection of the $x$ and $y$ point, but we do not know the angle yet. Geometrically, the angle, must be the same as the $(u, v, 0)$ make with the origin, so we can claim that

$x = \frac{2u}{u^2 + v^2 + 1}$ and $y = \frac{2v}{u^2 + v^2 + 1}$ as this choice of coordinate fits the angle requirement and the radical distance requirements.

In comparison, part (b) is a lot simpler. Just substitute $t = 0$ and $t = 1$ to the given parametization will yield the two required points.

For part (c), we substitute the line into the sphere to find intersections.

$\begin{eqnarray*} x^2 + y^2 + z^2 &=& 1 \\ (tu)^2 + (tv)^2 + (1 - t)^2 &=& 1 \\ (tu)^2 + (tv)^2 + (1 - 2t + t^2) &=& 1 \\ (tu)^2 + (tv)^2 - 2t + t^2 &=& 0 \\ (u^2 + v^2 + 1)t^2 - 2t &=& 0 \\ ((u^2 + v^2 + 1)t - 2)t &=& 0 \\ t &=& 0 \text{ or } \frac{2}{u^2 + v^2 + 1} \end{eqnarray*}$

That easily yield the parametization we wanted by substitute $t$ back to the formula:

$x = tu = \frac{2u}{u^2 + v^2 + 1}$

$y = tv = \frac{2v}{u^2 + v^2 + 1}$

$z = 1 - t = 1 - \frac{2}{u^2 + v^2 + 1} = \frac{u^2 + v^2 - 1}{u^2 + v^2 + 1}$

Story learnt? Solving things geometrically can be much harder.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 5

Problem:

Solution:

For part (a), just substitute the definition of the hyperbolic trigonometric function into the hyperbola.

$\begin{eqnarray*} & & x^2 - y^2 \\ &=& \cosh^2(t) - \sinh^2(t) \\ &=& (\frac{1}{2}(e^t + e^{-t}))^2 - (\frac{1}{2}(e^t - e^{-t}))^2 \\ &=& \frac{1}{4}((e^{2t} + 2 + e^{-2t}) - (e^{2t} - 2 + e^{-2t})) \\ &=& \frac{1}{4}(4) \\ &=& 1 \end{eqnarray*}$

Note that the hyperbola cover the whole y range, we also know that hyperbolic sine is monotonic and cover the whole $y$ range, so we know for each $y$ value, there is a corresponding $t$, so we have a corresponding $x$ as well. Note that as hyperbolic cosine is always positive, so it never covers the whole left hand side of the hyperbola.

For part (b), $x = 0$ does not touch the hyperbola, $x = 1$ touches the hyperbola once as a tangent, $y = 0$ cuts the hyperbola twice.

For part (c), consider the line $y = t(x + 1) = tx + t$, substitute this into the hyperbola, we get:

$\begin{eqnarray*} x^2 - y^2 &=& 1 \\ x^2 - (tx + t)^2 &=& 1 \\ x^2 - (t^2x^2 + 2t^2x + t^2)&=& 1 \\ (1 - t^2)x^2 - 2t^2x - t^2 &=& 1 \\ (1 - t^2)x^2 - 2t^2x - (t^2 + 1) &=& 0 \end{eqnarray*}$

Normally, we would have to solve this, but we already know one of the solution must be $(-1, 0)$, so we can simply use the sum of root formula.

$\begin{eqnarray*} -1 + x &=& \frac{-b}{a} = \frac{2t^2}{1-t^2} \\ x &=& \frac{2t^2}{1-t^2} + 1 \\ &=& = \frac{1 + t^2}{1 - t^2} \end{eqnarray*}$

Then we simply also computes $y$.

$\begin{eqnarray*} y &=& tx + t = t\frac{1 + t^2}{1 - t^2} + t \\ &=& \frac{t + t^3}{1 - t^2} + \frac{t-t^3}{1 - t^2} \\ &=& \frac{2t}{1 - t^2} \end{eqnarray*}$

The final parametrization is therefore $\left(\begin{array}{c}x \\ y\end{array}\right) = \left(\begin{array}{c}\frac{1 + t^2}{1 - t^2} \\ \frac{2t}{1 - t^2}\end{array}\right)$. It is interesting to compare it with the circle's parametrization as $\left(\begin{array}{c}x \\ y\end{array}\right) = \left(\begin{array}{c}\frac{1 - t^2}{1 + t^2} \\ \frac{2t}{1 + t^2}\end{array}\right)$

Part (d) is obvious now, of course the line cannot be the asymptote, that correspond to $t = \pm 1$.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 4

Problem:

Solution:

The first equation does not come with squares, so maybe it is easier to start with the first one.

$\begin{eqnarray*} x &=& \frac{t}{1+t} \\ x + tx &=& t \\ x &=& t - tx \\ &=& t(1 - x) \\ t &=& \frac{x}{1 - x} \end{eqnarray*}$

Now we can substitute $t$ into $y$ to eliminate $t$.

$\begin{eqnarray*} y &=& 1 - \frac{1}{t^2} \\ &=& 1 - \frac{1}{(\frac{x}{1 - x})^2} \\ &=& 1 - (\frac{1 - x}{x})^2 \\ &=& 1 - (\frac{1}{x} - 1)^2 \\ &=& 1 - (\frac{1}{x^2} - \frac{2}{x} + 1) \\ &=& \frac{2}{x} - \frac{1}{x^2} \\ x^2y &=& 2x - 1 \end{eqnarray*}$

For part (b), first of all note that $(1, 1)$ is in the variety. Note that by the equation $t = \frac{x}{1 - x}$, we can substitute any $x$ we want into the equation, except of course we cannot set $x = 1$. So for any point in the variety, we can find the corresponding $t$, therefore we know the parametric representation does cover all points but $(1, 1)$ on the variety.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 3

Problem:

Solution:

This is trivial, the solution, with parameter $s$, is

$\left(\begin{array}{c}x \\ y \end{array}\right) = \left(\begin{array}{c}s \\ f(s) \end{array}\right)$

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 2

Problem:

Solution:

The key trigonometry identity to use is the double angle formula:

$\begin{eqnarray*} \cos(2t) &=& 2\cos^2(t) - 1 \\ y &=& 2x^2 - 1 \end{eqnarray*}$

This is a parabola with vertex $(0, -1)$, it cuts the x-axis as $(-\frac{1}{\sqrt{2}}, 0)$ and $(\frac{1}{\sqrt{2}}, 0)$.
As $t \in [-\pi, \pi ]$, $x \in [-1, 1]$, $y \in [-1, 1]$.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 3 Exercise 1

Problem:

Solution:

Take the sum of the the equations, we have:

$\begin{eqnarray*} 2x + 3y - z &=& 1 \\ z &=& 2x + 3y - 1 \\ w &=& x + y + z - 2 \\ &=& x + y + (2x + 3y - 1) + 2 \\ &=& 3x + 4y + 1 \end{eqnarray*}$

Therefore the solutions are, in parameters $s$ and $t$, are

$\left(\begin{array}{c}x \\ y \\ z \\ w \end{array}\right) = \left(\begin{array}{c}s \\ t \\ 2s + 3t - 1 \\ 3s + 4t + 1 \end{array}\right)$

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 15

Problem:

Solution:

a)

The hint basically give out the answer.

Basic fact: Union or Intersection of two affine varieties is an affine variety.

Induction:

Base case is trivial, Union or Intersection of 1 affine variety is an affine variety, obviously.

Suppose the Union or Intersection of $k$ affine varieties is an affine variety, because of the basic fact, the Union or Intersection of $k + 1$ affine varieties is again an affine variety.

Therefore, by the principle of mathematical induction, the finite union and intersection is not an affine variety.

b)

We showed that the integer grid is not an affine variety, but it is an infinite union of a single points, which are affine varieties.

c)

We showed that the punctured line is not an affine variety, but a line and a point are both affine varieties and so that we have found an example.

d)

Just put all the governing polynomials together would work, of course, we need to rename the variables.

The proof that it works is trivial, a point that is in $V \times W$ must be a point that satisfy all the governing polynomials.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 14

Problem:

Solution:

a)

This is obvious, the arm cannot possibly reach anything outside the circle with radius 6.

b)

This is again obvious, the node between second and third arm has to stay on the circle with radius 5, the only remaining freedom is the third arm which can bring us anywhere in the annulus.

c)

We already know we are able to reach any point in the annulus, now we only need to worry about points in the inner circle with radius 4. Suppose we fold the second arm completely backwards to be parallel with the first arm, we can reach all points with a circle with radius 2.

On the other hand, if we can fix the angle between the first arm and the second arm to be at an angle such that the node of the second arm is of distance 3 from the origin, then we are done because now the last arm can cover all points between 2 and 4 from the origin.

To do that, we note that the first arm is distance 3 from the origin, the second arm is 2 distance from the first arm tip, and the second arm tip is again distance 3, so we form an isosceles triangle and therefore the angle is simply $\cos^{-1} \frac{1}{3}$.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 13

Problem:

Solution:

a)

I will skip this one, the picture is pretty obvious.

b) 3 variables.

The angle $\theta_1$ between the first arm and an arbitrary axis on the plane
The angle $\theta_2$ between the second arm and first arm
The angle $\theta_3$ between the third arm and the second arm.

c)

If we define the "state" as the space for all the angles, then they are all independent! They are in the space of $[-\pi, \pi]^3$, no equation is needed to govern them.

However, if we are thinking about the "state" as position and orientation, then it can get quite complex, we can still reason it with affine transforms, we simply stack the transforms up.

$\left(\begin{array}{ccc} \cos \theta_1 & -\sin \theta_1 & 0 \\ \sin \theta_1 & \cos \theta_1 & 0 \\ 0 & 0 & 1\end{array}\right) \left(\begin{array}{ccc} 1 & 0 & 3 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array}\right) \left(\begin{array}{ccc} \cos \theta_2 & -\sin \theta_2 & 0 \\ \sin \theta_2 & \cos \theta_2 & 0 \\ 0 & 0 & 1\end{array}\right) \left(\begin{array}{ccc} 1 & 0 & 2 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array}\right) \left(\begin{array}{ccc} \cos \theta_3 & -\sin \theta_3 & 0 \\ \sin \theta_3 & \cos \theta_3 & 0 \\ 0 & 0 & 1\end{array}\right) \left(\begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array}\right)$

The product is the affine transformation that takes a coordinate (in homogeneous coordinates) in the third arms frame (i.e. origin at third arm's tip, x coordinate axis parallel with the third arm) to the world frame.

d)

The intuitive dimension of the variety of states is 3.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 12

Problem:

Solution:

This problem is adopted from a Calculus textbook.

Find the points on circle $x^2 + y^2 = 45$ that are closest and farthest from $(1, 2)$.

The function to optimize is $(x - 1)^2 + (y - 2)^2$. We do not take the square root as optimizing the square is the same as optimizing the square root.

The corresponding Lagrangian is

$L(x, y, \lambda) = (x - 1)^2 + (y - 2)^2 - \lambda(x^2 + y^2 - 45)$.

The partial derivatives must be 0, therefore, we have

$\begin{eqnarray*} \frac{\partial L}{\partial x} = 2(x - 1) - 2\lambda x &=& 0 \\ \frac{\partial L}{\partial y} = 2(y - 2) - 2\lambda y &=& 0 \\ x^2 + y^2 &=& 45 \end{eqnarray*}$

The system is not hard to solve manually, but it would be really nice to see this can be solved automatically with Groebner basis.

For the sake of completeness, let's solve this system manually, we see

$2(x - 1) - 2\lambda x = 0 \implies x(1-\lambda) = 1$
$2(y - 2) - 2\lambda y = 0 \implies y(1-\lambda) = 2$

Dividing them, we get $x = 2y$, this make things very easy now.

$\begin{eqnarray*} x^2 + y^2 &=& 45 \\ x^2 + (2x)^2 &=& 45 \\ 5x^2 &=& 45 \\ x &=& \pm 3 \\ y &=& \pm 6 \end{eqnarray*}$

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 11

Problem:

Solution:

The two trivial solutions for both odd and even powers are

$x = 0$, $y = 1$
$x = 1$, $y = 0$

The two more trivial solutions for only even powers are

$x = 0$, $y = -1$
$x = -1$, $y = 0$

Suppose we have a non-trivial solution in $\mathbf{Q}$, suppose the answer is $x = \frac{p}{q}$, $y = \frac{r}{s}$, then we have

$(\frac{p}{q})^n + (\frac{r}{s})^n = 1$

 Multiply both side by $q^ns^n$, we get a non-trivial solution for Fermat's last theorem.

$(ps)^n + (rq)^n = (qs)^n$.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 10

Problem:

Solution:

According to my proof for exercise 6 in section 1, we have proved the following fact.

If a polynomial vanish on the whole integer grid, it must be the zero polynomial.

Now it is easy to prove this with that fact. Suppose $\mathbf{Z}^n$ is an affine variety, it must be written as a finite collection of polynomials. All of its polynomials must vanish on the integer grid, and therefore all of them must be zero polynomials, but then $\mathbf{Z}^n$ does not contain non-integer points yet its polynomial must also vanish there as well, so we have reached a contradiction and that $\mathbf{Z}^n$ is not an affine variety.

This problem also give us a nice corollary, we know any single point is an affine variety. Now we show that the infinite union of affine variety need not be an affine variety. (Although finite unions are)

Integral (2)

Problem:

$\int{\sqrt{\frac{4 - x}{4 + x}}dx}$

Solution:

This one is not easy, I am thinking about this identity

$\sqrt{\frac{1 - \sin \theta}{1 + \sin\theta}} = \frac{1-\tan \frac{\theta}{2}}{1+\tan \frac{\theta}{2}}$

Therefore I let $x = 4 \sin \theta$, that gives $dx = 4 \cos \theta d\theta$, the integral becomes

$\begin{eqnarray*} &=& \int{\sqrt{\frac{4 - 4\sin\theta}{4 + 4\sin\theta}}4 \cos \theta d\theta} \\ &=& \int{2\sqrt{\frac{1 - \sin\theta}{1 + \sin\theta}}4 \cos \theta d\theta} \\ &=& \int{2\frac{1-\tan \frac{\theta}{2}}{1+\tan \frac{\theta}{2}}4 \cos \theta d\theta} \\ &=& \int{2\frac{1-\tan \frac{\theta}{2}}{1+\tan \frac{\theta}{2}}4 \frac{1-\tan^2 \frac{\theta}{2}}{1+\tan^2 \frac{\theta}{2}} d\theta} \end{eqnarray*}$

Now it is quite obvious that we should do the t - substitution

$\begin{eqnarray*} t &=& \tan \frac{\theta}{2} \\ dt &=& \sec^2 \frac{\theta}{2} \frac{1}{2} d \theta\\ dt &=& (1 + t^2) \frac{1}{2} d \theta \\ d \theta &=& \frac{2tdt}{1 + t^2} \\ \end{eqnarray*}$

$\begin{eqnarray*} & & \int{2\frac{1-\tan \frac{\theta}{2}}{1+\tan \frac{\theta}{2}}4 \frac{1-\tan^2 \frac{\theta}{2}}{1+\tan^2 \frac{\theta}{2}} d\theta} \\ &=& \int{2\frac{1-t}{1+t}4 \frac{1-t^2}{1+t^2} \frac{2tdt}{1 + t^2}} \\ &=& 8\int{\frac{1}{1+t^2} - \frac{2t}{(1 + t^2)^2}dt} \end{eqnarray*}$

The first term can be solved by substitute $t = \tan \phi$, $dt = \sec^2 \phi d\phi$

$\begin{eqnarray*} & & \int{\frac{1}{1+t^2}dt} \\ &=&\int{\frac{1}{1+\tan^2 \phi}\sec^2 \phi d\phi} \\ &=&\int{\frac{1}{\sec^2 \phi}\sec^2 \phi d\phi} \\ &=&\int{d\phi} \\ &=&\phi \end{eqnarray*}$

The second term can be solved by substitute $u = 1 + t^2$, $du = 2tdt$

$\begin{eqnarray*} & & \int{\frac{2t}{(1 + t^2)^2}dt} \\ &=& \int{\frac{1}{u^2}du} \\ &=& \frac{-1}{u} \end{eqnarray*}$

Putting them together, we have

$\begin{eqnarray*} & & \int{\sqrt{\frac{4 - x}{4 + x}}dx} \\ &=& 8\int{\frac{1}{1+t^2} - \frac{2t}{(1 + t^2)^2}dt} \\ &=& 8(\phi + \frac{1}{u}) \\ &=& 8(\phi + \frac{1}{1 + t^2}) \end{eqnarray*}$

Now we have $t = \tan \phi, t = \tan \frac{\theta}{2}$, so we simply have $\phi = \frac{\theta}{2}$

$\begin{eqnarray*} & & 8(\frac{\theta}{2} + \frac{1}{1 + t^2}) \\ &=& 8(\frac{\theta}{2} + \frac{1}{1 + \tan^2 \frac{\theta}{2}}) \\ &=& 8(\frac{\theta}{2} + \frac{1}{\sec^2 \frac{\theta}{2}}) \\ &=& 8(\frac{\theta}{2} + \cos^2 \frac{\theta}{2}) \\ &=& 8(\frac{\theta}{2} + \frac{1 + \cos \theta}{2}) \\ &=& 4(\theta + 1 + \cos \theta) \end{eqnarray*}$

Now constant can be dropped for indefinite integral, and $x = 4 \sin \theta$, so finally we have

$\begin{eqnarray*} & & 4(\theta + \cos \theta) \\ &=& 4(\arcsin(\frac{x}{4}) + \cos \theta) \\ &=& 4(\arcsin(\frac{x}{4}) + \sqrt{1 - \sin^2 \theta}) \\ &=& 4(\arcsin(\frac{x}{4}) + \sqrt{1 - (\frac{x}{4})^2}) \end{eqnarray*}$

There we go, what a complicated problem!