Field Theory - Theorem 2

 

Algebraic:

There exists a polynomial $f$ with coefficients in field $K$ such that $f(u)=0$. In this case, we say $u$ is algebraic over $K$.

Transcendental:

There exists no polynoimal $f$ with coefficients in field $K$ such that $f(u)=0$ with the exception of zero polynomial. In this case, we say $u$ is trascendental over $K$.

A field $L$ containing field $K$ is considered algebraic over $K$ if every element of $L$ is algebraic over $K$.
 
Theorem 2:
 
Suppose $K$ is a field, $u$ an element of larger field, and suppose that $u$ is algebraic over $K$. Let $f$ be a monic polynomial with coefficients in $K$ of the minimal degree $n$ such that $f(u)=0$. Then
(a) $f$ is unique.
(b) $f$ is irreducible over $K$.
(c) $1,u,u^2,\cdots,u^{n-1}$ form a vector space basis for $K(u)$ over $K$.
(d) $[K[u]:K]=n$.
(e) A polynomial $g$ with coefficients in $K$ satisfies $g(u)=0$ iff $g$ is a multiple of $f$.

Proof:

Assume that there is another polynomial $f'$, and let $f_0=f-f'$. Since, both $f$ and $f'$ are monic, the leading terms gets eliminated and $f_0$ becomes a polynomial of degree less than $n$. This means, we have $f_0$ a polynomial with degree less than $n$ going to zero whenever $f,f'$ go to zero. However, this is a contradiction $f$ is supposed to be of minial degree.

$f$ is irreducible. Assume otherwise and write $f=hg$ where $h,g$ are polynomials of degree (obviously less than n). When $f$ goes to zero, one or both of $g,h$ will go to zero, thus contradicting the fact that $f$b is of minimal degree.

Linear relation between $1,u,u^2,\cdots,u^{k-1}$ indicates that there exists a polynomial $g(u)=0$ of degree less than $n$, thus proving that $1,u,u^2,\cdots,u^{n-1}$ form a linearly independent set for $K$.

All we need to show is that $T=K[u]$ is a field. Given all multiplicatons and additions we have been performing so far, not difficult to see that $T$ is a ring.

Next we need to show that $u^k \in T$. Clearly, $1,u,u^2,\cdots,n^{n-1} \in T$.
Now set an element $u^{k-1} = 1+u+u^2+\cdots+u^{n-1}$. Multiply both sidees by $u$. Then, $u^k = u+u^2+u^3+\cdots+u^n$. Since $u^n$ can be expressed in terms of $1,u,u^2,\cdots,u^{n-1}$, we have $u^k$ as a linear combination of these basis elements. Hence $u^k \in T$.

To show that $T$ is a field, we also need to show that every element has an inverse. Indeed if $g$ is another polynomial of degree less than $n$, given that $f$ is irreducible, we will have $gcd(f,g)=1$ which means there exists polynomials $r,s$ of degree less than $n$ such that $fr+gs = 1$. Clear that when $f$ gets sent to zero, the expression $gs=1$ indicating that $s$ is inverse of the $g$.

If $g$ is another polynomial with coefficients in $K$ such that $g(u)=0$ then $g$ is a multiple of $f$. If $g$ is not a multiple of $f$ (which is irreducible) then $gcd(f,g)=0$. This means that there are two polynomials $r,s$ such that $fr+gs=1$. Since $f(u)=0$, then $fr=0$ and $g(u)=0$ means $gs=0$ leading to contradiction. Hence, $g$ is a multiple of $f$.

Field extensions-Theorem 1

Notice the following tower of fields.

 Base field is $K=Q$, intermediate field is $L=Q(\sqrt{3})$ and top field is $M=Q(\sqrt{7})$.
Field $L=Q(\sqrt{3})=\{a+b\sqrt{3}|a,b \in Q\}$.
Field $M=Q(\sqrt{3})=\{a+b\sqrt{3}+c\sqrt{7}+d\sqrt{7x3=21}|a,b,c,d \in Q\}$. 

Note that the field $M$ is a vector space over $L$ and $K$. Indeed, from the expression $M=Q(\sqrt{3})=\{a+b\sqrt{3}+c\sqrt{7}+d\sqrt{7x3=21}|a,b,c,d \in Q\}$ one can see that $M$ as vector space over $K$ has dimension $4$.
That is $[M:K]=4$.
There is another way of expression $M$ as a vector space over $L$. 

Letting $u_1,u_2$ be elements of this form $u_1=a+b\sqrt{3}$ and $u_2=c+d\sqrt{3}$, one can express elements of $M$ as $u_1+\sqrt{7}(u_2)$.
That is $[M:L]=2$. Similarly $[L:K]=2$. Thus,
$[M:K]=[M:L][L:K]=2*2=4$.

First theorem of Field extensions formalizes these observations.

Theorem 1:Let $K,L,M$ be fields with $K\subset L \subset M$. Then $[M:K]$ is finite if and only if both $[M:L]$ and $[L:K]$  are finite and in that case $[M:K]=[M:L][L:K]$.
Proof is a generalization of above observations.
Assume that $[M:K]$ is finite, then consider $L$ as subspace of $M$ over $K$. As a subspace of finite vector space $[L:K]$ is finite. Any basis that spans $M$ over $K$ (for example, $\{a,b,c,d\}$ in above fields), also spans $M$ over $L$; hence, $[M:L]$ is also finite.

Assume the vector space $M$ over $L$ has $[M:L]=m$ and $L$ over $K$ has $[L:K]=n$, then we need to show that $[M:K]=mn$.

Let $z \in M$. $z$ can be expressed as $z=\sum_i u_i h_i$ where $h_i \in L$. And $h_i=\sum_j c_{ij}v_j$. Putting all this together, $z = \sum_i \sum_j c_{ij}u_i v_j$. $i,j$ range over $m$ and $n$. This is the spanning set for $M$ over $K$.

To show this is independent, we need to show that whenever $\sum_{ij} c_{ij} u_i v_j = 0$ we need to have $c_{ij}=0$.
$\sum_{ij} c_{ij} u_i v_j$ can be rewritten as $\sum_i h_i u_i$ where $h_i \in L$. Since $u_i$ form a basis for $M$ over $L$, we must have each $h_i=0$ and since this means $\sum c_{ij} v_j=0$ and independence of $v_j$ leads to each $c_{ij}=0$.

One consequence of this thoerem is that if the order of $M/L$ is a prime, then this precludes any fields between $M$ and $L$.

More examples of Galois groups

Let $F=Q$. Now, this time consider the polynomial $(x^2-2)(x^2-3)$. Clearly the roots of the polynomial are $\pm\sqrt{2},\pm\sqrt{3}$. The splitting field for this polynomials is $E(\sqrt{2},\sqrt{3}) = \{a+b\sqrt{2}+c\sqrt{3}+d\sqrt{6}|a,b,c,d, \in Q\}$. Notice, that $x^2=\sqrt{6}$ is also a root.

Dimension of $E$ is $4$ and easy to see that $E$ is a vector space over $F$.

To derive Galois group, we start listing out the automorphisms of the extended field $E$ that fix $F$.

Thus we are seeking $\sigma$ that takes a root of $x^2-2$ to a root of $x^2-2$. That is $\sigma(\sqrt{2})=\pm\sqrt{2}$. Similarly $\sigma(\sqrt{3}) = \pm \sqrt{3}$

The value of both these roots can be taken independently. The following lists all the automorphisms of that fix $F$.

Thus $G=Gal(E/F)=\{\sigma_1=Id,\sigma_2,\sigma_3,\sigma_4\}$

It is interesting to note that we have intermediate fields between $F$ and $E$. Naming them as $B_1=F$ and $B_5=E$, we have other fields $B_2=Q(\sqrt{2}),B_3=Q(\sqrt{3}),B_4=Q(\sqrt{6})$.

These nested fields are shown below:

 As vector spaces $Q(\sqrt{2})$ has dimension $2$. Same is true of other intermediate field $Q(\sqrt{3})$.Field $Q(\sqrt{2},\sqrt{3})$ has dimension $4$ over $E=Q$ has dimensions $2$ over $Q(\sqrt{2})$ and $Q(\sqrt{3})$.

These examples lay foundation for understanding theorems about field extensions.

Simple example of a Galois Group:

Let $Q$ be a field of rationals. Let $x^2-2$ be a polynomial with rational coefficients. That is, let $x^2-2 \in Q[x]$.

Since $\sqrt{2}$ is not a rational, the roots of equation $x^2-2$ will not be in $Q$. However, if we extend this field by adjoining $\sqrt{2}$, then we have a new field over which the polynomial $x^2-2$ has roots. This new field $Q(\sqrt{2})$ is called splitting field of the polynomial. Elements of this field have form $\{a+b\sqrt{2}|a,b \in Q\}$.

Let $K=Q,L=Q(\sqrt{2})$. 

We ask for all automorphisms of $L$  that fix $K$, namely $\phi:L \rightarrow L$ that fix $K$. These automorphisms must take a root of above polynomial to a root. Thus, we have two automorphisms.

$Q(\sqrt{2})$ should map to $\sqrt{2}$. Identity automorphism $Id$ meets this criteria. 

Consider automorphism $\phi_1(\sqrt{2})\rightarrow -\sqrt{2}$. Clearly, this will carry elements of $Q(a+b\sqrt{2}) \rightarrow a - b \sqrt{2}$. 

If we collect all these automorphisms into a set, we have a set consisting of $\{Id,\phi_1\}$

Clearly $\phi_1\circ\phi_1 = Id$. Hence, above set forms  a group of order $2$.  This Automorphism group is called Galois group denoted as $Gal(L/K)$.

 

Linear Discriminant Analysis -1

Computing classification means computing class posterior probabilities \(Pr(G|X)\) - that is probability that class is G given input X. If \(f_k(x)\) is the class conditional density of \(X\) in class \(Gk\) and if \(\pi_k\) is prior probability, then Bayes theorem gives, \[\begin{equation} Pr(G=k|X=x) = \frac{f_k(x)\pi_k}{\sum_{l=1}^K f_l(x)\pi_l} \end{equation}\]
Depending on the models for class density, different techniques emerge.

* linear and quadratic discrimnant analysis use Gaussian densities
* Mixture of Gaussians lead to non-linear decision boundaries.
* Navie Bayes models assume that each class density is product of marginal densities.

Derivations:
Suppose that each class density is modelled as multivariate Gaussian. \[\begin{equation} f_k(x)=\frac{1}{(2\pi)^{p/2} |\Sigma_k|^{1/2}} e^{-\frac{1}{2}(x-\mu_k)^T\Sigma_k^{-1}(x-\mu_k)} \end{equation}\] Clear that \[\begin{equation} Pr(G=k|X=x) = \frac{f_k(x)\pi_k}{\sum_{l=1}^K f_l(x)\pi_l} \\ Pr(G=l|X=x) = \frac{f_l(x)\pi_l}{\sum_{p=1}^K f_p(x)\pi_p} \\ \frac{Pr(G=k|X=x)}{Pr(G=l|X=x)} = \frac{f_k(x)\pi_k}{f_l(x)\pi_l} \\ log\left(\frac{Pr(G=k|X=x)}{Pr(G=l|X=x)} \right) = log\frac{f_k(x)}{f_l(x)}+log\frac{\pi_k(x)}{\pi_l(x)} \end{equation}\] Now expression \(\frac{f_k(x)}{f_l(x)}\) can be simplified as follows. Note \(\Sigma\) is assumed to be same for all the classes. \[\begin{equation} log\left(\frac{f_k(x)}{f_l(x)}\right) = \left[ -\frac{1}{2}(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)+\frac{1}{2}(x-\mu_l)^T\Sigma^{-1}(x-\mu_l)\right] \end{equation}\] And \[\begin{equation} = -\frac{1}{2} [x^T\Sigma^{-1}x-x^T\Sigma^{-1}\mu_k-\mu_k^T\Sigma^{-1}x+\mu_k^T\Sigma^{-1}\mu_k - x^T\Sigma^{-1}x + x^T\Sigma^{-1}\mu_k + \mu_l \Sigma^{-1} x - \mu_l^T\Sigma^{-1}\mu_l ] \end{equation}\] Next \[\begin{equation} = \frac{1}{2} [-x^T\Sigma^{-1}x + x^T\Sigma^{-1}\mu_k + \mu_k^T\Sigma^{-1}x -\mu_k^T\Sigma^{-1}\mu_k+x^T\Sigma^{-1}x-x^T\Sigma^{-1}\mu_l-\mu_l^T\Sigma^{-1}x + \mu_l^T\Sigma^{-1}\mu_l ] \end{equation}\]
Before simplying, we should note the following:

• Since \(\Sigma\) is a covariance matrix and since covariance between \(i\) and \(j\) is same as \(j\) and \(i\), then \(\Sigma^T=\Sigma = \Sigma^{-1}\).
• The mean matrices \(\mu_k\) for class \(k\) and \(\mu_l\) for class \(l\) are \(p \times 1\) matrix.
• Terms such as \(\mu_k \Sigma^{-1}\mu_l\) have dimensions \(1\times p * p \times p * p \times 1=1\times 1\) or scalars aka reals.

Second term and fifth term with leading \(x^T\) can be simplified as \[\begin{equation} \frac{1}{2}x^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation}\] Collecting third and seventh terms \(x\) at end. \[\begin{equation} \left[\frac{1}{2}(\mu_k^T - \mu_l^T)\Sigma^{-1}x\right]^T = \frac{1}{2}x^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation}\] The remaining terms are \[\begin{equation*} -\frac{1}{2}\mu_k^l\Sigma^{-1}\mu_l+\frac{1}{2}\mu_l^T\Sigma^{-1}\mu_l+\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_l-\frac{1}{2}(\mu_k^T\Sigma^{-1}\mu_l)^T \\ = \frac{1}{2}(\mu_k+\mu_l)^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation*}\] Combining all those simplification, \[\begin{equation*} log\left(\frac{Pr(G=k|X=x)}{Pr(G=l|X=x)}\right) = log\left(\frac{\pi_k}{\pi_l}\right) \\ -\frac{1}{2}(\mu_k+\mu_l)^T\Sigma^{-1}(\mu_k-\mu_l)+x^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation*}\] At the line that divides class \(k,l\) has probabilities \(Pr(G=k|X=x)=Pr(G=l|X=x)\) \[\begin{equation*} log(1)=0=log(\pi_k)-log(\pi_l) - \frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k+x^T\Sigma^{-1}\mu_k + \frac{1}{2}\mu_l^T\Sigma^{-1}\mu_l-x^T\Sigma^{-1}\mu_l \end{equation*}\] From here, the linear discriminant can be written as \[\begin{equation} \delta_k=log(\pi_k)-\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k+x^T\Sigma^{-1}\mu_k \end{equation}\]

Sets of Measure Zero.

Heard the saying - What happens in Las Vegas, stays in Las Vegas? Sets of measure zero are kind of like that.

For example, say $f(x),g(x)$ are functions that are equal to each other in measurable space $E$, except on a subset $N$. Say a given measure on ``disagreeable'' space $N$ is equal to zero. Now $N$ is like Las Vegas and we are given license to forget about what happens in this space $N$ and assert that $f(x)=g(x)$ a.e where a.e stands for almost everwhere. To be more precise (just to prevent extra point from being leaked out of your exam paper!), we need to state $f(x)=g(x)$ a.e[$\mu$]. That is we need to specify which measure.

Mathematically, \begin{equation} \mu\{x:f(x)\neq g(x)\} = 0 \end{equation}

where $x \in N$. The above criteria specifies the points of $N$. Here $f$ ~ $g$ and it is not too difficult to prove that this is an equivalence relation.

Reflexive property: Clearly $f$ ~ $f$. The disagreeable set $N$ in this case is a null set and measure of null set is $0$. $f=f$ on the whole set. Symmetric: Clearly $f$ ~ $g$ also means that set of disagreeable space remains same when we switch $f$ to the right. Reflexive: Say $f$ ~ $g$ and let $N_1$ be the disagreeable set. Say $g$ ~ $h$ and let $N_2$ be the disagreeable set, then $N_1 \cup N_2$ where $f,g,h$ are not equal to each other. Hence $f$ ~ $h$.

Note all the above statements were made based on a property that $f=g$. Generally, we don't have to be specific about a property. Above assertions and proofs hold in a more abstract sense, that is for any property $P$.

R&C - Lebesgue's Dominated Convergence Theorem

Dominated Conv Theorem

If \(f \in \mathcal{L}(\mu)\), then \[\begin{equation} \left|\int_X f d\mu \right| \leq \int_x|f| d\mu \end{equation}\]

Proof uses the previously proven identity -

If \(f\) is a complex measurable function on \(X\), there is a complex measurable function \(\alpha\) on \(X\) such that \(|\alpha|=1\) and \(f=\alpha|f|\). This is an extension of property of complex numbers.

Start off by setting \(z=\int_X f d\mu\). Then there is another complex number \(\alpha\) such that \(|\alpha|=1\) and \(\alpha z= |z|\).

Let \(u\) be real part of \(\alpha f\). Then, \(u \leq |\alpha f|=|f|\). Hence,

\[\begin{align*} \left| \int_X f d\mu\right| = |z|=\alpha z=\alpha \int_X f d\mu \\ = \int_X \alpha f d\mu = \int_X u d\mu \leq \int_X |f| d\mu \end{align*}\] Suppose \(\{f_n\}\) is a sequence of complex measurable functions on \(X\) such that \[\begin{equation} f(x) = lim_{n \rightarrow \infty} f_n(x) \end{equation}\] exists for every \(x \in X\). If there is a function \(g \in \mathcal{L^1(\mu)}\) such that \[\begin{equation} |f_n(x)| \leq g(x) \text{ } (n=1,2,\cdots|x \in ) \end{equation}\] then \(f \in \mathcal{L^1(\mu)}\), \[\begin{equation} lim_{n \rightarrow \infty}\int_X |f_n - f| d\mu = 0 \end{equation}\] and \[\begin{equation} lim_{n \rightarrow \infty} \int_X f_n d\mu = \int_X f d\mu \end{equation}\]

Clear that \(|f| \leq g\). Since \(f_n\) are measurable, the limit \(f\) is measurable, \(f \in \mathcal{L^1(\mu)}\). \[\begin{align*} |f-f_n| \leq |f|+|f_n| \leq 2g \end{align*}\] This means, \(2g - |f_n - f|\) is a sequence of functions whose range is in \([0,\infty]\). Hence, precondition to satisfy Fatou’s lemma is satisfied. This yield \[\begin{align*} \int_X 2g d\mu \leq lim_{n \rightarrow \infty}inf \int_X(2g-|f_n-f|)d\mu \\ =\int_X 2g d\mu + lim_{n \rightarrow \infty}inf\left( - \int_X |f_n - f| d\mu\right) \\ = \int_X 2g d\mu - lim sup_{n \rightarrow \infty} \int_X |f_n - f| d\mu \end{align*}\] Taking advantage of finiteness of \(\int 2g d\mu\), \[\begin{align*} lim sup_{n \rightarrow \infty}\int_X |f_n - f| d\mu \leq 0 \end{align*}\] If sequence of nonnegative real numbers fails to converge to \(0\), then its upper limit is positive. Then above equation implies \[\begin{align*} lim _{n \rightarrow \infty}\int_X |f_n - f| d\mu = 0. \end{align*}\] Hence, \[\begin{align*} lim_{n \rightarrow \infty} \int_X f_n d\mu = \int_X f d\mu \end{align*}\]