Writing tips

These are some writing tips, I learnt from the ENGR 202S course at Stanford.

Friday, $12^{th}$ April, $2013$:

1. Hyphen: Hyphens are mostly used to break single words into parts, or to join ordinarily separate words (usually two adjectives) into single words. Spaces should not be placed between a hyphen and either of the words it connects except when using a suspended or "hanging" hyphen (e.g. nineteenth- and twentieth-century writers). Hyphen is also used to line break when a word is left halfway hanging in a line.
2. En dash: The length of this is the typical length of $n$, which approximately $2$ hyphens. Used to indicate range. For e.g., $10 \text{--}20$.
3. Em dash: The length of this is the length of a typical $m$, which is approximately $3$ hyphens. Used to demarcates a break of thought or some similar interpolation stronger than the interpolation demarcated by parentheses, which is in turn stronger than a comma.
4. etc.: $\underbrace{\text{Et}}_{\text{and}} \overbrace{\text{cetera}}^{\text{other things}}$ Always ends with a period and is separated from the previous object with a comma. "For e.g., a, b, c, etc., have been studied by ..."
5. et al.: $\underbrace{\text{Et}}_{\text{and}} \overbrace{\text{aliaa}}^{\text{other people}}$ Always ends with a period and is separated from the previous object with a comma. "For e.g., a, b, c, et al., have worked ..."
6. Difference between which and that: Consider the following two sentences. $$\text{We looked at the instructions that were at the end of the manual.}$$ $$\text{We looked at the instructions, which were at the end of the manual.}$$ Both the sentences are correct, but they convey different meanings. $$\text{The first one: The manual had many instructions and we followed the ones given at the end.}$$ $$\text{The second one: We followed the instructions given in the manual. The instructions were given}$$ $$\text{at the end of the manual.}$$ Now some conventions. The above is in US English. In US English, "that" and "which" are never interchangeable and "which" is always preceded by a comma. In UK English, "that" can be replaced by "which" without comma. Hence, in UK English, the comma before which is all the more important not to change the meaning of the sentence.

Friday, $19^{th}$ April, $2013$:

Questions:

"Our fast, new, stable algorithm for large-scale linear inversion problem relies on $\mathcal{H}$-matrix algebra and is applicable when the number of unknowns $m$ is large --- around $100,000$ --- and the number of measurements is of the order of $100 \text{--} 500$."

1. The above sentence has two "and"s. Is that right?
2. Should there be a comma before "and"?
3. When do we need to use a colon and semicolon?
4. 
   

Eulerian tour theorem

This post looks at Eulerian cycle theorem in graph theory.

We first define a few terms.

A walk is an alternating sequence of vertices and edges, beginning and ending at a vertex with the constraint that each edge between two vertices must be incident on these two vertices. Essentially, it means moving in a graph along the edges in a continuous fashion. For example, a typical walk of length $n$ is of the form $$v_1 e_1 v_2 e_2 v_3 e_3 \cdots v_{n-1} e_{n-1} v_n e_n v_{n+1} \tag{$\star$}$$ where $e_j$ is incident to $v_j$ and $v_{j+1}$.

A cycle is a walk with the beginning and ending vertices being the same, i.e., $(\star)$ with $v_{n+1} = v_1$.

A walk where no edge is repeated is called a trail, i.e., $e_j \neq e_k$ for $j \neq k$ in $(\star)$.

A closed trail, i.e., the beginning and ending vertices being the same and no edge is repeated, i.e., $e_j \neq e_k$ for $j \neq k$ and $v_{n+1} = v_1$ in $(\star)$, is termed as a tour or a circuit.

An Eulerian trail is a trail passing through all the edges in the graph.

An Eulerian tour is a tour passing through all the edges in the graph.

Eulerian tour theorem: Let $G$ be a connected undirected graph, then the following two statements are equivalent:

1. $G$ has an Eulerian tour.
2. All the vertices in $G$ are even.

If the graph has loops, i.e., an edge connecting the same vertex the above still holds true, provided we interpret that every loop counts to the degree of the vertex twice.

Proof: We will prove it for graphs without loops since the loops do not make any difference.

$1 \implies 2$. Since $G$ has an Eulerian tour, every time we enter a vertex we need to exit it. Further, the tour doesn't repeat an edge. Hence, every vertex has even degree.

$2 \implies 1$. This proceed by induction on the number of edges. The base case is when the number of edges is $2$. This corresponds to a graph with $2$ vertices and $2$ edges between these two vertices. Clearly, this has an Eulerian tour. Assume that all graphs with number of edges less than $m$ and with each vertex having even degree has an Eulerian tour. Now we will show that a graph with $m$ number of edges and with each vertex having even degree has an Eulerian tour. Pick any vertex. There exists a tour starting and ending at this vertex. To see this, if this were not to be possible, then we would end at a vertex from which we cannot escape. However, this can never happen since each vertex has even degree. Hence, we can pick a tour starting and ending at the same vertex. Let this tour be $T$ and be of length $n$ and say $v_1 e_1 v_2 e_2 \ldots v_{n-1} e_{n-1} v_n e_n v_1$. Once we have this we are done. Now remove these edges from the graph. We will then have at most $n$ connected components, say $C_1, C_2, \ldots, C_k$, where $k \leq n$. Now by induction hypothesis, there is a Eulerian tour on each of these connected components. Now we will obtain the Eulerian tour on the entire graph $G$. Now lets get back to the tour $T$ and start at $v_1$. Find the first time this tour intersects one of the connected components. Once it hits the connected component, complete the tour within this connected component and return to the place where the tour hit this connected component. Repeat this till we have visited all the connected components and finally complete the tour. Note that adding loops play no role since if we were to have loop(s) at a vertex, whenever we hit that vertex finish of the loop(s) and continue.

Handshaking lemma

The Handshaking lemma states that any finite undirected graph has an even number of vertices with odd-degree. This follows immediately from a more fundamental result, namely, the degree sum formula.

Degree sum formula: Given an undirected graph $G$, with the set of vertices $V$ and edges $E$, we have$$\sum_{v \in V} \text{deg}(v) = 2\vert E \vert$$ If the graph has loops, i.e., an edge connecting the same vertex the above still holds true, provided we interpret that every loop counts to the degree of the vertex twice. (Sometimes, degree sum formula is also called the handshaking lemma)

Proof: We will prove the result when the graph has no loops. Once we prove it for graphs with no loops, the result is evident for graphs with loops since every time we add a loop, the degree of a vertex increases by $2$ and so does the right hand side.

Let $\mathbb{I}(v_i,v_j)$ be the indicator function that denotes if there is an edge between the vertices $v_i$ and $v_j$. We then have
$$\sum_{v_i \in V;v_j \in V} \mathbb{I}(v_i,v_j) = 2 \vert E \vert \tag{$\star$}$$This is because each edge is incident to two vertices and hence each edge is counted twice in the above summation. However, $(\star)$ can also be rewritten as $$\sum_{v_i \in V} \left(\sum_{v_j \in V} \mathbb{I}(v_i,v_j)\right) = 2 \vert E \vert$$Now note that $\displaystyle \left(\sum_{v_j \in V} \mathbb{I}(v_i,v_j) \right)$ is nothing but the degree of the vertex $v_i$, since each time a vertex is adjacent to the vertex $v_i$, the count increases by $1$. Hence, we have what we want, i.e.,$$\sum_{v \in V} \text{deg}(v) = 2\vert E \vert$$This immediately implies that there has to be an even number of vertices with odd-degree. Let $V_e$ be the set of vertices with even degree and $V_o$ be the set of vertices with odd degree. We then have that$$\sum_{v \in V_e} \text{deg}(v) + \sum_{v \in V_o} \text{deg}(v) = 2\vert E \vert \tag{$\dagger$}$$Since every vertex in $V_e$ has an even degree, we have $\sum_{v \in V_e} \text{deg}(v)$ to be an even number. This and $(\dagger)$ implies $\sum_{v \in V_o} \text{deg}(v) \,\,\, (\perp)$ has to be even. Now each of $\deg(v)$ in $(\perp)$ is odd. If $\vert V_o \vert$ were to be odd, then $\sum_{v \in V_o} \text{deg}(v)$ will be odd (since an odd number of odd integers when added up will give an odd number), contradicting the fact that it has to be even.

$\displaystyle \int_0^{\pi} \ln (1-2a \cos(x) + a^2) dx$

This is a nice integral from the $13^{th}$ annual Stanford Mathematics tournament.

Compute the integral
$$\int_0^{\pi} \ln \left(1-2a \cos(x) + a^2\right) dx$$

Solution:

Moor xu has presented $5$ different solutions here. We look at another way to compute the integral.
Let $$I(a) = \displaystyle \int_0^{\pi} \ln \left(1-2a \cos(x) + a^2\right) dx$$ Some preliminary results on $I(a)$. Note that we have $$I(a) = \underbrace{\displaystyle \int_0^{\pi} \ln \left(1+2a \cos(x) + a^2\right) dx}_{\spadesuit} = \overbrace{\dfrac12 \displaystyle \int_0^{2\pi} \ln \left(1-2a \cos(x) + a^2\right) dx}^{\clubsuit}$$ $(\spadesuit)$ can be seen by replacing $x \mapsto \pi-x$ and $(\clubsuit)$ can be obtained by splitting the integral from $0$ to $\pi$ and $\pi$ to $2 \pi$ and replacing $x$ by $\pi+x$ in the second integral.
Now let us move on to our computation of $I(a)$.
\begin{align}
I(a^2) & = \int_0^{\pi} \ln \left(1-2a^2 \cos(x) + a^4\right) dx = \dfrac12 \int_0^{2\pi} \ln \left(1-2a^2 \cos(x) + a^4\right) dx\\
& = \dfrac12 \int_0^{2\pi} \ln \left((1+a^2)^2-2a^2(1+ \cos(x))\right) dx = \dfrac12 \int_0^{2\pi} \ln \left((1+a^2)^2-4a^2 \cos^2(x/2)\right) dx\\
& = \dfrac12 \int_0^{2\pi} \ln \left(1+a^2-2a \cos(x/2)\right) dx + \dfrac12 \int_0^{2\pi} \ln \left(1+a^2+2a \cos(x/2)\right) dx
\end{align}
Now replace $x/2=t$ in both integrals above to get
\begin{align}
I(a^2) & = \int_0^{\pi} \ln \left(1+a^2-2a \cos(t)\right) dt + \int_0^{\pi} \ln \left(1+a^2+2a \cos(t)\right) dt = 2I(a)
\end{align}
Now for $a \in [0,1)$, this gives us that $I(a) = 0$. This is because we have $I(0) = 0$ and $$I(a) = \dfrac{I(a^{2^n})}{2^n}$$ Now let $n \to \infty$ and use continuity to conclude that $I(a) = 0$ for $a \in [0,1)$. Now lets get back to our original problem. Consider $a>1$. We have
\begin{align*}
I(1/a) & = \int_0^{\pi} \ln \left(1-\dfrac2{a} \cos(x) + \dfrac1{a^2}\right)dx\\
& = \int_0^{\pi} \ln(1-2a \cos(x) + a^2) dx - 2\int_0^{\pi} \ln(a)dx\\
& = I(a) - 2 \pi \ln(a)\\
& = 0  \tag{Since $1/a < 1$, we have $I(1/a) = 0$}
\end{align*}
Hence, we get that
$$I(a) = \begin{cases} 2 \pi \ln(a) & a \geq 1 \\ 0 & a \in [0,1] \end{cases}$$