Math fixes: spaces in inline math, deprecated commands (non-environment forms of cases, pmatrix, et al)

algmyr · algmyr · commit 15f809b697a1 · 2018-08-17T11:28:42.000+02:00
diff --git a/src/algebra/euclid-algorithm.md b/src/algebra/euclid-algorithm.md
@@ -18,7 +18,7 @@ The algorithm was first described in Euclid's "Elements" (circa 300 BC), but it
 
 The algorithm is extremely simple:
 
-$$gcd(a, b) = \cases{a,&if $b = 0$\cr gcd(b, a\mod b),&otherwise}$$
+$$gcd(a, b) = \begin{cases}a,&if $b = 0$\cr gcd(b, a\mod b),&otherwise\end{cases}$$
 
 ## Implementation
 
@@ -76,7 +76,7 @@ $$
 So, recalling that $d \mid b$, we obtain the system:
 
 $$
-\cases{d \mid b,\cr d \mid (a \mod b)\cr}
+\begin{cases}d \mid b,\cr d \mid (a \mod b)\cr\end{cases}
 $$
 
 Now we use the fact that for any three numbers $p$, $q$, $r$, if $p\mid q$ and $p\mid r$ then $p\mid gcd(q, r)$, In our case, we get:
diff --git a/src/algebra/extended-euclid-algorithm.md b/src/algebra/extended-euclid-algorithm.md
@@ -32,10 +32,10 @@ $$ g = b \cdot x_1 + a \cdot \left( y_1 - \left\lfloor \frac{b}{a} \right\rfloor
 
 We found the values of $x$ and $y$:
 
-$$ \cases{
+$$ \begin{cases}
 x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor \cdot x_1 \cr
 y = x_1
-} $$
+\end{cases} $$
 
 ## Implementation
 
diff --git a/src/algebra/fft.md b/src/algebra/fft.md
@@ -581,7 +581,7 @@ If there isn't a match, then at least a character is different, which leads that
 ### String matching with wildcards
 
 This is an extension of the previous problem.
-This time we allow that the pattern contains the wildcard character $ * $, which can match every possible letter.
+This time we allow that the pattern contains the wildcard character $*$, which can match every possible letter.
 E.g. the pattern $a*c$ appears in the text $abccaacc$ at exactly three positions, at index $0$, index $4$ and index $5$.
 
 We create the exact same polynomials, except that we set $b_i = 0$ if $P[m-i-1] = *$.
diff --git a/src/algebra/fibonacci-numbers.md b/src/algebra/fibonacci-numbers.md
@@ -89,11 +89,11 @@ As these two formulas would require very high accuracy when working with fractio
 
 It is easy to prove the following relation:
 
-$$\pmatrix{F_{n-1} & F_{n} \cr} = \pmatrix{F_{n-2} & F_{n-1} \cr} \cdot \pmatrix{0 & 1 \cr 1 & 1 \cr}$$
+$$\begin{pmatrix}F_{n-1} & F_{n} \cr\end{pmatrix} = \begin{pmatrix}F_{n-2} & F_{n-1} \cr\end{pmatrix} \cdot \begin{pmatrix}0 & 1 \cr 1 & 1 \cr\end{pmatrix}$$
 
-Denoting $P \equiv \pmatrix{0 & 1 \cr 1 & 1 \cr}$, we have:
+Denoting $P \equiv \begin{pmatrix}0 & 1 \cr 1 & 1 \cr\end{pmatrix}$, we have:
 
-$$\pmatrix{F_n & F_{n+1} \cr} = \pmatrix{F_0 & F_1 \cr} \cdot P^n$$
+$$\begin{pmatrix}F_n & F_{n+1} \cr\end{pmatrix} = \begin{pmatrix}F_0 & F_1 \cr\end{pmatrix} \cdot P^n$$
 
 Thus, in order to find $F_n$, we must raise the matrix $P$ to $n$. This can be done in $O(\log n)$ (see [Binary exponentiation](./algebra/binary-exp.html)).
 
diff --git a/src/algebra/primitive-root.md b/src/algebra/primitive-root.md
@@ -32,11 +32,11 @@ Furthermore, the number of primitive roots modulo $n$, if there are any, is equa
 
 A naive algorithm is to consider all numbers in range $[1, n-1]$. And then check if each one is a primitive root, by calculating all its power to see if they are all different. This algorithm has complexity $O(g . n)$, which would be too slow. In this section, we propose a faster algorithm using several well-known theorems.
 
-From previous section, we know that if the smallest number $k$ for which $g^k \equiv 1 \pmod n$ is $ \phi (n)$, then $g$ is a primitive root. Since for any number $a$ relative prime to $n$, we know from Euler's theorem that $a ^ { \phi (n) } \equiv 1 \pmod n$, then to check if $g$ is primitive root, it is enough to check that for all $d$ less than $ \phi (n)$, $g^d \not \equiv 1 \pmod n$. However, this algorithm is still too slow.
+From previous section, we know that if the smallest number $k$ for which $g^k \equiv 1 \pmod n$ is $\phi (n)$, then $g$ is a primitive root. Since for any number $a$ relative prime to $n$, we know from Euler's theorem that $a ^ { \phi (n) } \equiv 1 \pmod n$, then to check if $g$ is primitive root, it is enough to check that for all $d$ less than $\phi (n)$, $g^d \not \equiv 1 \pmod n$. However, this algorithm is still too slow.
 
-From Lagrange's theorem, we know that the index of any number modulo $n$ must be a divisor of $ \phi (n)$. Thus, it is sufficient to verify for all proper divisor $d \, | \, \phi (n)$ that $g^d \not \equiv 1 \pmod n$. This is already a much faster algorithm, but we can still do better.
+From Lagrange's theorem, we know that the index of any number modulo $n$ must be a divisor of $\phi (n)$. Thus, it is sufficient to verify for all proper divisor $d \, | \, \phi (n)$ that $g^d \not \equiv 1 \pmod n$. This is already a much faster algorithm, but we can still do better.
 
-Factorize $ \phi (n) = p_1 ^ {a_1} ... p_s ^ {a_s}$. We prove that in the previous algorithm, it is sufficient to consider only the values of $d$ which has the form $ \frac { \phi (n) } {p_j}$. Indeed, let $d$ be any proper divisor of $ \phi (n) $. Then, obviously, there exists such $j$ that $d \, | \, \frac { \phi (n) } {p_j}$, i.e. $d . k = \frac { \phi (n) } {p_j}$. However, if $g^d \equiv 1 \pmod n$, we would get:
+Factorize $\phi (n) = p_1 ^ {a_1} ... p_s ^ {a_s}$. We prove that in the previous algorithm, it is sufficient to consider only the values of $d$ which has the form $\frac { \phi (n) } {p_j}$. Indeed, let $d$ be any proper divisor of $\phi (n)$. Then, obviously, there exists such $j$ that $d \, | \, \frac { \phi (n) } {p_j}$, i.e. $d . k = \frac { \phi (n) } {p_j}$. However, if $g^d \equiv 1 \pmod n$, we would get:
 
 $g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d . k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$.
 
@@ -56,7 +56,7 @@ Shoup (1990, 1992) proved, assuming the [generalized Riemann hypothesis](http://
 
 ## Implementation
 
-The following code assumes that the modulo `p` is a prime number. To make it works for any value of `p`, we must add calculation of $\phi (p) $. 
+The following code assumes that the modulo `p` is a prime number. To make it works for any value of `p`, we must add calculation of $\phi (p)$. 
 
 ```cpp
 int powmod (int a, int b, int p) {
diff --git a/src/algebra/sieve-of-eratosthenes.md b/src/algebra/sieve-of-eratosthenes.md
@@ -39,7 +39,7 @@ Now, let's evaluate this sum using the integral of a same function over $k$ from
 
 $$\sum_{k = 2}^{\frac n {\ln n}} \frac 1 {k \ln k} \approx \int_2^{\frac n {\ln n}} \frac 1 {k \ln k} dk.$$
 
-The antiderivative for the integrand is  $ \ln \ln k$. Using a substitution and removing terms of lower order, we'll get the result:
+The antiderivative for the integrand is  $\ln \ln k$. Using a substitution and removing terms of lower order, we'll get the result:
 
 $$\int_2^{\frac n {\ln n}} \frac 1 {k \ln k} dk = \ln \ln \frac n {\ln n} - \ln \ln 2 = \ln(\ln n - \ln \ln n) - \ln \ln 2 \approx \ln \ln n.$$
 
diff --git a/src/combinatorics/inclusion-exclusion.md b/src/combinatorics/inclusion-exclusion.md
@@ -135,7 +135,7 @@ $$3^n - (3 \cdot 2^n - 3 \cdot 1 + 0)$$
 
 Consider the following equation:
 $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20$$
-where $ 0 \le x_i \le 8 (i = 1,2,\ldots 6)$.
+where $0 \le x_i \le 8 (i = 1,2,\ldots 6)$.
 
 Task: count the number of solutions to the equation.
 
diff --git a/src/geometry/lines-intersection.md b/src/geometry/lines-intersection.md
@@ -8,21 +8,21 @@ You are given two lines, described as coefficients $A_1, B_1, C_1$ and $A_2, B_2
 
 If two lines are not parallel, they intersect. To find their intersection point, we need to solve the following system of linear equations:
 
-$$ \cases{ A_1 x + B_1 y + C_1 = 0, \cr
-A_2 x + B_2 y + C_2 = 0. } $$
+$$ \begin{cases} A_1 x + B_1 y + C_1 = 0, \cr
+A_2 x + B_2 y + C_2 = 0. \end{cases} $$
 
 Using Cramer's rule, we immediately find the solution for the system, which will give us the required intersection point of the lines:
 
-$$ x = - \frac{ \left|\matrix{C_1&B_1 \cr C_2&B_2}\right| }{ \left|\matrix{A_1&B_1 \cr A_2&B_2}\right| } = - \frac{ C_1 B_2 - C_2 B_1 }{ A_1 B_2 - A_2 B_1 }, $$
-$$ y = - \frac{ \left|\matrix{A_1&C_1 \cr A_2&C_2}\right| }{ \left|\matrix{A_1&B_1 \cr A_2&B_2}\right| } = - \frac{ A_1 C_2 - A_2 C_1 }{ A_1 B_2 - A_2 B_1 }. $$
+$$ x = - \frac{ \begin{vmatrix}C_1&B_1 \cr C_2&B_2\end{vmatrix} }{ \begin{vmatrix}A_1&B_1 \cr A_2&B_2\end{vmatrix} } = - \frac{ C_1 B_2 - C_2 B_1 }{ A_1 B_2 - A_2 B_1 }, $$
+$$ y = - \frac{ \begin{vmatrix}A_1&C_1 \cr A_2&C_2\end{vmatrix} }{ \begin{vmatrix}A_1&B_1 \cr A_2&B_2\end{vmatrix} } = - \frac{ A_1 C_2 - A_2 C_1 }{ A_1 B_2 - A_2 B_1 }. $$
 
 If the denominator equals $0$, i.e.
 
-$$ \left|\matrix{A_1&B_1 \cr A_2&B_2}\right| = A_1 B_2 - A_2 B_1 = 0 $$
+$$ \begin{vmatrix}A_1&B_1 \cr A_2&B_2\end{vmatrix} = A_1 B_2 - A_2 B_1 = 0 $$
 
 then either the system has no solutions (the lines are parallel and distinct) or there are infinitely many solutions (the lines overlap). If we need to distinguish these two cases, we have to check if coefficients $C$ are proportional with the same ratio as the coefficients $A$ and $B$. To do that we only have calculate the following determinants, and if they both equal $0$, the lines overlap:
 
-$$ \left|\matrix{ A_1 & C_1 \cr A_2 & C_2 }\right|, \left|\matrix{ B_1 & C_1 \cr B_2 & C_2 }\right| $$
+$$ \begin{vmatrix} A_1 & C_1 \cr A_2 & C_2 \end{vmatrix}, \begin{vmatrix} B_1 & C_1 \cr B_2 & C_2 \end{vmatrix} $$
 
 ## Implementation
 
diff --git a/src/string/suffix-array.md b/src/string/suffix-array.md
@@ -9,22 +9,22 @@ A **suffix array** will contain integers that represent the **starting indexes**
 
 As an example look at the string $s = abaab$.
 All suffixes are as follows
-$$\begin{align}
-0. ~&~ abaab \\\\
-1. ~&~ baab \\\\
-2. ~&~ aab \\\\
-3. ~&~ ab \\\\
-4. ~&~ b
-\end{align}$$
+$$\begin{array}{ll}
+0. & abaab \\\\
+1. & baab \\\\
+2. & aab \\\\
+3. & ab \\\\
+4. & b
+\end{array}$$
 
 After sorting these strings:
-$$\begin{align}
-2. ~&~ aab \\\\
-3. ~&~ ab \\\\
-0. ~&~ abaab \\\\
-4. ~&~ b \\\\
-1. ~&~ baab
-\end{align}$$
+$$\begin{array}{ll}
+2. & aab \\\\
+3. & ab \\\\
+0. & abaab \\\\
+4. & b \\\\
+1. & baab
+\end{array}$$
 
 Therefore the suffix array for $s$ will be $(2,~ 3,~ 0,~ 4,~ 1)$.
 
@@ -46,13 +46,13 @@ it is enough to append an arbitrary character to the end of the string which is
 It is common to use the symbol $\\$$.
 Then the order of the sorted cyclic shifts is equivalent to the order of the sorted suffixes, as demonstrated here with the string $dabbb$.
 
-$$\begin{align}
-1. ~~ abbb$d ~&~ abbb \\\\
-4. ~~ b$dabb ~&~ b \\\\
-3. ~~ bb$dab ~&~ bb \\\\
-2. ~~ bbb$da ~&~ bbb \\\\
-0. ~~ dabbb$ ~&~ dabbb
-\end{align}$$
+$$\begin{array}{lll}
+1. & abbb\\$d & abbb \\\\
+4. & b\\$dabb & b \\\\
+3. & bb\\$dab & bb \\\\
+2. & bbb\\$da & bbb \\\\
+0. & dabbb\\$ & dabbb
+\end{array}$$
 
 Since we are going to sort cyclic shifts, we will consider **cyclic substrings**.
 We will use the notation $s[i \dots j]$ for the substring of $s$ even if $i > j$.
