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 the field in question. If has elements then which is commutative. Suppose now that any field with fewer elements than is commutative. The following lemma will be useful:
Lemma If is a finite field and is a subfield of which is commutative then there exists a positive integer such that . (where we denote by the number of elements of )
Suppose is irreducible, monic and all roots of have absolute value at most . Then is a cyclotomic polynomial.
Proof: It suffices to prove that every root of is a root of unity. If
consider the family of polynomials
The coefficients of are algebraic integers, since they are calculated using multiplications and additions starting from . On the other hand, the coefficients of are symmetric polynomials in , so they are rational, and therefore integers.
Furthermore, since then the coefficient of in satisfies
This bounds the coefficients of independently of . Since it follows that we can only have a finite number of polynomials in the family .
Theorem. Let be a finite group and be a prime number. Then . (we denote by the cardinal of ).
Proof: Denote . Then since if we cnoose the first elements arbitrarily in then the last element can be chosen in a unique way such that the equation is satisfied. Note that is stable under cyclic permutations of the elements of a vector. Therefore the action of on by
is well defined.
We will need the following lemma:
Lemma. If is a group (with prime) and acts on then
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.
You have a table and on each row and column you need to have squares coloured with color and squares coloured with color 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.
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 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.
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 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.
Given points in the plane we can study the problem
For the solution is known and for a triangle which has an angle less than 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 , if we have a convex quadrilateral, then a simple triangle inequality argument proves that the optimal position for 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 is not a hard task, and I will do that in the end of this post.
Problem 1. The probability that an animal reacts positively to an injection is . 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.