Every finite field is commutative – Wedderbrun’s Theorem

April 11, 2014 Leave a comment

Wedderbrun’s Theorem Every finite field is commutative.

Proof: The statement of the theorem is very simple to understand, yet it is hard (if you’re not an expert) to imagine why the axioms of a field and the finiteness assumption allow us to deduce that the field is commutative.

We will prove the theorem by induction over the number of elements of our field. Denote {K} the field in question. If {K} has {2} elements then {K=\{0,1\}} which is commutative. Suppose now that any field {L} with fewer elements than {K} is commutative. The following lemma will be useful:

Lemma If {L} is a finite field and {K\neq L} is a subfield of {L} which is commutative then there exists a positive integer {n \geq 2} such that {|L|=|K|^n}. (where we denote by {|X|} the number of elements of {X})

Read more…

Kronecker’s Theorem regarding Cyclotomic Polynomials

April 6, 2014 Leave a comment

Suppose {f \in \Bbb{Z}[X]} is irreducible, monic and all roots of {f} have absolute value at most {1}. Then {f} is a cyclotomic polynomial.

Proof: It suffices to prove that every root of {f} is a root of unity. If

\displaystyle f(X)=(X-\alpha_1)...(X-\alpha_r)

consider the family of polynomials

\displaystyle f_n(X) =(X-\alpha_1^n)...(X-\alpha_r^n).

The coefficients of {f_n} are algebraic integers, since they are calculated using multiplications and additions starting from {\alpha_1,...,\alpha_r}. On the other hand, the coefficients of {f_n} are symmetric polynomials in {(\alpha_i)}, so they are rational, and therefore integers.

Furthermore, since {|\alpha_i| \leq 1} then the coefficient {b_k} of {X^k} in {f_n} satisfies

\displaystyle |b_k| \leq \sum_{1\leq i_1,...,i_k\leq r} |\alpha_{i_1}^n...\alpha_{i_k}^n| \leq {r\choose k}.

This bounds the coefficients of {f_n} independently of {n}. Since {f_n \in \Bbb{Z}[X]} it follows that we can only have a finite number of polynomials in the family {(f_n)}.

Read more…

Group actions and applications to number theory

April 6, 2014 Leave a comment

Theorem. Let {G} be a finite group and {p} be a prime number. Then {|G|^{p-1} \equiv |\{x \in G : x^p=e\}|}. (we denote by {|X|} the cardinal of {X}).

Proof: Denote {X = \{(g_1,...,g_p) \in \Bbb{Z}^p : g_1...g_p=e\}}. Then {|X|=|G|^{n-1}} since if we cnoose the first {p-1} elements arbitrarily in {G} then the last element can be chosen in a unique way such that the equation is satisfied. Note that {X} is stable under cyclic permutations of the elements of a vector. Therefore the action of {\Bbb{Z}_p} on {X} by

\displaystyle j\cdot (g_1,...,g_p)=(g_{j+1},...,g_{j+p})

is well defined.

We will need the following lemma:

Lemma. If {G} is a {p} group (with {p} prime) and {G} acts on {X} then

\displaystyle |X| \equiv |\{x \in X : G\cdot x = \{x\}\}| \pmod p.

Read more…

Two more mind games solved using Matlab

March 31, 2014 Leave a comment

After doing this, solving the Sudoku puzzle with Matlab, I wondered what else can we do using integer programming? Many of the mind games you can find on the Internet can be modelled as matrix problems with linear constraints. I will present two of them, as well as their solutions, below. The game ideas are taken from www.brainbashers.com. Note that in order to use the pieces of code I wrote you need to install the YALMIP toolbox.

1. Three in a row

You have a {2n \times 2n} table {(n \geq 3)} and on each row and column you need to have {n} squares coloured with color {A} and {n} squares coloured with color {B} such that no three squares taken vertically or horizontally have the same color. In the begining you are given the colors of some of the square such that it leads to a unique solution satisfying the given properties. The goal is to find the colors corresponding to each small square starting from the ones given such that the end configuration satisfies the given properties.

Read more…

Solve a Sudoku Puzzle using Matlab

March 29, 2014 Leave a comment

There was a time when I loved to solve Sudoku puzzles. It happened sometimes to find some really difficult puzzles, which I was unable to solve. Having a program which solves Sudoku puzzles is cool, but knowing how it works is cooler.

There are multiple types of solvers. One can imagine to take each free cell in a Sudoku puzzle and associate to it the set of integers in \{1,2,...,9\} which can lie in there (see the picture below). If the set of possible values contains only one element, then you have found the element corresponding to that cell. If not, then the program needs to make one guess, and see if it gets him to a contradiction. If it arrives at a contradiction, return to the choice step and choose another option, and this needs to be done recursively, which can take huge amounts of time.

sudoku_solver-148625-1

One other method which can be implemented in Matlab is to use the matrix structure of the Sudoku table and write the constraints of non repetition on lines, columns and 3 \times 3 blocks as linear constraints. Once all these constraints are well defined, you can call a semidefinite programming solver to find a solution. A semidefinite programming solver looks to find the vector which optimizes a given cost functions under certain constraints. A good sudoku puzzle has only one solution, and therfore every admissible input which satisfies the constraints is a solution. This means that the cost function doesn’t matter here.

I will present the implementation using YALMIP. You can find another equivalent Matlab implementation here.

Read more…

Simple optimization problem regarding distances

March 27, 2014 Leave a comment

Given {n} points {A_1,...,A_n} in the plane we can study the problem

\displaystyle \min_M MA_1+...+MA_n.

For {n=3} the solution is known and for a triangle which has an angle less than {120^\circ} is the Toricelli (or Fermat) point, which lies at the intersection of the circumcircles of the equilateral triangles built outside the triangle having the sides of the triangle as support.

For {n=4}, if we have a convex quadrilateral, then a simple triangle inequality argument proves that the optimal position for {M} is the intersection of the diagonals.

In general, we cannot precisely say what is the position of the solution. Providing a numerical algorithm which computes the optimal position of {M} is not a hard task, and I will do that in the end of this post.

 

Read more…

Two examples of Probability applications

March 25, 2014 Leave a comment

Problem 1. The probability that an animal reacts positively to an injection is {0.75}. Eight random animals have been injected. Calculate the probability of the following events:

a) No animal has a positive reaction;

b) Exactly two animals have a positive reaction;

c) At most two animals have a positive reaction;

d) At least two animals have a positive reaction.

 

Read more…

Follow

Get every new post delivered to your Inbox.

Join 324 other followers

%d bloggers like this: