Matrices over finite Fields

1.1 MATRICES OVER FINITE FIELDS

Question 1: (program is on page 9)

Below are the outputs of the program with input data 3 and 13 respectively. The program stores the inverses of the non-zero elements of the field F in an array of length p-1.

p=3

The inverse of 1 is 1

The inverse of 2 is 2

p=13

The inverse of 1 is 1

The inverse of 2 is 7

The inverse of 3 is 9

The inverse of 4 is 10

The inverse of 5 is 8

The inverse of 6 is 11

The inverse of 7 is 2

The inverse of 8 is 5

The inverse of 9 is 3

The inverse of 10 is 4

The inverse of 11 is 6

The inverse of 12 is 12

A simple modification to speed up the procedure is for each, in the range, we store b, which is the inverse of in the range,

and at the same time we store as the inverse of b. This should be done for all <b.

Question 2:

The procedure of Question 1 calculates and stores the inverses of non-zero elements of field F in an array of length p-1. A mean of p/2 operations are needed in order to calculate the inverse of each element. There are p-1 elements, so the total number of operation are f(p)=p(p-1)/2, hence the complexity of the procedure is of order.

Gaussian Elimination:

Question 3: (program is on page 9)

In Question 3 I used Gaussian elimination to turn the matrix into echelon form, by using simple row operations. I also used the program for Question 1 to turn the first element of each row to 1. Then the rank is very easily calculated by the program by counting the number of non-zero rows and the row space are those non-zero rows.

When the input is (mod 7), then the output is:

echelon_form =

1 4 0 5 3

0 0 1 2 6

0 0 0 1 3

0 0 0 0 0

A basis for the rank of the matrix is:

( 1 4 0 5 3)

( 0 0 1 2 6)

( 0 0 0 1 3)

The rank of the matrix is 3

When the input is (mod 29), then the output is:

echelon_form =

1 17 1 20 3 9

0 1 14 28 14 18

0 0 1 16 1 19

0 0 0 0 0 1

A basis for the rank of the matrix is:

( 1 17 1 20 3 9)

( 0 1 14 28 14 18)

( 0 0 1 16 1 19)

( 0 0 0 0 0 1)

The rank of the matrix is 4

Kernels and Annihilators:

Question 4: (program is on page 11)

A is an m x n matrix and x=() an nx1 column vector over f. The kernel of A denoted kerA, is the space of solutions to Ax=0.

The program I created first turns matrix A into echelon form, by using the program I created for Question 3. Then the dimension of the kernel is calculated by using the Rank-Nullity theorem that states that dim(kerA)+dim(ImA)=n , where n is the dimension of the column space. dim(ImA)=rank(A). The rank of A is r and is found by using the program I created for Question 3. Therefore dim(kerA)=n-r. Using this result we construct an (n-r) x n matrix U with all entries zeros. The program the identifies the values of l(k), where , and at the same time, for i, where , the number 1 is placed in U(i,j) position where and we increase i by 1, where i denotes the row number.

U will be used to construct a basis for the kernel of A. Using the algorithm U(i,l(k))=U(i,l(k))-E(k,j)*U(i,j), where E(i,j) is the echelon form of the original matrix A. As a result an (n-r) x n matrix U is formed. The row vectors of the matrix, when transpose, form (n-r) column vectors which are the basis for the kernel of A.

When the input is (mod 7) then the output is:

A basis for the kernel of the matrix, transpose, is:

( 0, 1, 1, 0, 1)

The Kernel of the matrix is 1.

When the input is (mod 29) then the output is:

A basis for the kernel of the matrix, transpose is:

The Kernel of the matrix is 0

Question 5:

The relationship between the dimensions of andis dim()+dim()=n, where n is the dimension of the column space of the matrix A, and U is a subspace of the space of row vectors

Question 6:

U is the row space of the matrix (mod 7) and is obtained in Question 3. . By sing the program in Question 4, and having as input, we obtained , which is the basis for the kernel of . The output we get is:

A basis for the kernel of the matrix, transpose, is:

( 3, 1, 0, 0, 0)

( 5, 0, 0, 4, 1)

The Kernel of the matrix is 2.

We then use the output of Question 4 as an input to the program i.e is the new input. So by using the program of Question 4 we will obtained the basis for the kernel of the matrix . i.e . The output of the program is:

A basis for the kernel of the matrix, transpose is:

( 0, 0, 1, 0, 0)

( 2, 1, 0, 1, 0)

( 4, 2, 0, 0, 1)

The Kernel of the matrix is 3

Then by using the program that I created in Question 3 to turn the matrix into echelon form and having as an input we have as an output:

1 4 0 4 0

0 0 1 0 0

0 0 0 1 3

{ } are the basis for U:

(1 4 0 5 3)

(0 0 1 2 6)

(0 0 0 1 3)

(1 4 0 4 0)

(0 0 1 0 0)

(0 0 0 1 3)

By observation we see that:

These row operations leave the row space of the matrix unaltered, so the set of vectors { } span the same space as the set of vectors { }. Also, this shows that u1,u2,u3, hence . But the dim(U)=3 and the dim()=3. Therefore =.

Question 7: (program is on page 12)

The program I created has as input matrices U and W and the mod(p).

I use the program I created for Question 3, with matrices A and B as input to get the row spaces U and W, respectively as matrices.

Suppose U is an f x n matrix and W is an h x n matrix. I create a new matrix where the first f row vectors of the matrix are the row vectors of U and the following h row vectors of the matrix are the row vectors of W. The new matrix is an (f+h) x n matrix and is used as an input to the program I created for Question 3. As a result we have as an output the basis of the row space of U+W.

We are given that . If we replace U with and W with we get . By using the program I created for Question 4, I find the basis for the kernel of U and W. Then I construct a new matrix with the first row vectors to be the row vectors of the basis for U and the following row vectors to be the row vectors of the basis for W. The new matrix is the input for the program I created for Question 4 and the output is the basis for

From linear Algebra course we found that:

Therefore, the dimensions of plus the dimension of, should always equal to the dimension of U plus the dimension of W.

The matrices we are interested are : (mod 7) and (mod 7). When these matrices are the input for the program I created in Question 3, the output is U and W respectively, which are used as an input to the program I created for Question 7 and the output is:

A basis for U is:

( 1 4 0 5 3)

( 0 0 1 2 6)

( 0 0 0 1 3)

A basis for W is:

( 1 6 5 2 3)

( 0 1 6 2 0)

( 0 0 1 0 6)

( 0 0 0 1 0)

A basis for U+W is:

( 1 4 0 5 3)

( 0 1 6 2 0)

( 0 0 1 2 6)

( 0 0 0 1 3)

( 0 0 0 0 1)

A basis for the intersection of U and W is:

( 2 1 6 1 0)

( 4 2 4 0 1)

Equation * is satisfied.

The matrices we are interested are : (mod 29) and (mod 29). When these matrices are the input for the program I created in Question 3, the output is U and W respectively, which are used as an input to the program I created for Question 7 and the output is:

A basis for U is:

( 1 4 2 4 4 2)

( 0 1 0 1 0 4)

( 0 0 1 0 1 4)

( 0 0 0 1 0 3)

A basis for W is:

( 1 0 5 2 1 3)

( 0 1 5 4 1 2)

( 0 0 1 4 4 0)

( 0 0 0 1 5 5)

( 0 0 0 0 1 4)

( 0 0 0 0 0 1)

A basis for U+W is:

( 1 4 2 4 4 2)

( 0 1 0 1 0 4)

( 0 0 1 0 1 4)

( 0 0 0 1 0 3)

( 0 0 0 0 1 6)

( 0 0 0 0 0 1)

A basis for the intersection of U and W is:

( 3 6 1 0 0 0)

( 0 4 0 1 0 0)

( 4 4 0 0 1 0)

( 0 1 0 0 0 1)

Equation * is satisfied.

Using matrix (mod5). I use the program I created for Question 3 to compute U, the row space of, and the program I created for Question 4 to obtained W, the kernel of . U and W are used as an input to the program I created for Question 7 and the output is:

A basis for U is:

( 1 0 4 0 0 3 1)

( 0 1 0 3 0 0 3)

( 0 0 1 0 2 3 0)

( 0 0 0 1 2 2 4)

A basis for W is:

( 3 1 3 3 1 0 0)

( 4 1 2 3 0 1 0)

( 4 4 0 1 0 0 1)

A basis for U+W is:

( 1 0 4 0 0 3 1)

( 0 1 0 3 0 0 3)

( 0 0 1 0 2 3 0)

( 0 0 0 1 2 2 4)

( 0 0 0 0 1 2 1)

A basis for the intersection of U and W is:

( 3 4 1 2 3 1 0)

( 1 3 2 3 4 0 1)

Equation * is satisfied.

Question 8

In the third example U is the row space of and W the kernel of , written as a space of row vectors. From linear algebra , meaning that . For all , . U is a subspace of , therefore . If a vector v belongs to , v belongs to the span of both U and W, therefore , meaning that .

When we are working over GF(p) we see from figure 12, that can have a basis which it is non-zero, something that will be surprising for someone working over the real numbers.

Appendix (Program listing)

Program used in Question 1

function x=modinv(p)

% This is a function to find x such that ax=1 mod(p)

% a is the non-zero element of F

% p is the length of the array

x=zeros(1,p-1);

for a=1:1:p-1

find = false;

i=1;

k=mod(a*i,p);

while i<p

if x(a)~= 0

find = true;

break

elseif k==1

x(a)=i;

x(i)=a;

find = true;

break

else

i=i+1;

k=mod(a*i,p);

end

end

if find == false;

x(a)= find;

end

end

x;

n=length(x);

for j=1:n

fprintf('The inverse of %2d is %2d\n',j,x(j))

end

Program used in Question 3

For computing the rank

function f=rank1(a,p)

b=echelon(a,p); %Function to turn the matrix into echelon form

rowspace = [];

d =size(a);

g=sum(b');

for i=1:d(1) %Function to collect the basis of the row space

if g(i)~=0

rowspace = [(rowspace);(b(i,:))];

end

end

N=size(rowspace);

echelon_form=b %Displays the echelon form

c=rowspace;

fprintf(' A basis for the rank of the matrix is

:\n',c)

k=size(rowspace);

for i=1:k(1) %Function to display the basis of the row space

fprintf('(%2d',rowspace(i,1));

for j=2:k(2)

fprintf('%4d',rowspace(i,j));

end

fprintf(')\n');

end

fprintf('\n The rank of the matrix is %2d\n\n',N(1))%Function to display the rank

f=N(1);

To turn the matrix into echelon form

function f=echelon(A,p)

% A is the original matrix used as an input

% p is the value of the mod(p)

clc

k=modinv(p); % modinv calculates the inverses for all elements x*modp

N=size(A);

flug=0;

check=0;

i=1;

for j=1:N(2)

A(:,:) = mod(A(:,:),p); %Function to calculate the matrix modp

if i<=N(1)

if A(i,j)== 0

w=0;

if ( N(1) >= i+1 )

A(i+1+w,j);

while i+1+w<=N(1) && A(i+1+w,j) == 0

w=w+1;

if N(1)== i+1+w

flug=1;

break

end

end

end

if i+1+w<=N(1) && A(i+1+w,j)~=0; % Function to transpose row i with row i+1+w

temp=A(i,:);

A(i,:)=A(i+1+w,:);

A(i+1+w,:)=temp;

check=1;flug=0;

else

check=0;

flug=1;

end

end

if i<=N(1) && A(i,j)~= 0

flug=0;

d=k(A(i,j));

A(i,:)= A(i,:)*d; % Function to turn the A(i,j) to 1

A(:,:) = mod(A(:,:),p);

for l=i+1:N(1)

if A(l,j)~=0

c=k(A(l,j)); %Function to multiply row l by the element c

A(l,:)= A(l,:)*c;

A(:,:) = mod(A(:,:),p);

A(l,:) = A(l,:) - A(i,:); %Function to subtract row i from row l

A(:,:) = mod(A(:,:),p);

else

A(:,:) = mod(A(:,:),p);

end

end

i=i+1;

end

end

end

A(:,:) = mod(A(:,:),p);

f=A(:,:);

Program used in Question 4

function f=kernel1(a,p)

% This function finds the basis of the kernel of matrix a

% p is such that a*mod(p)

E=echelon(a,p);

r=rank1(a,p);

clc

N=size(a);

U=zeros(N(2)-r,N(2));

i=1;

d=1;

for j=1:N(2)

if i<=N(1) && E(i,j)==1

l(i)=j;

i=i+1;

else

U(d,j)=1;

d=d+1;

end

end

for i=1:N(2)-r

for k=r:-1:1

for j=l(k)+1:N(2)

U(i,l(k))=U(i,l(k))-E(k,j)*U(i,j);

U(i,l(k))=mod(U(i,l(k)),p);

end

end

end

N=size(U);

c=U;

fprintf('A basis for the kernel of the matrix, transpose

is:\n',c)

for i=1:N(1) %Function to display the basis of the null space

fprintf('(%2d',U(i,1));

for j=2:N(2)

fprintf(',%4d',U(i,j));

end

fprintf(')\n');

end

fprintf('\n The Kernel of the matrix is %2d\n\n',N(2)-r) %Function to display the dimension of the kernel

Programs used in Question 7

function doublerank(u,w,p)

e=[u;w] %function to created a new matrix that contains all the elements of the matrices u and w

f=rank2(e,p);

l=kernel2(u,p);

m=kernel2(w,p);

h=[l;m];

R=kernel2(h,p);

fprintf('A basis for U is:\n')

N=size(u);

for i=1:N(1) %Function to display the basis of the row space ofU

fprintf('(%2d',u(i,1));

for j=2:N(2)

fprintf('%4d',u(i,j));

end

fprintf(')\n');

end

fprintf('A basis for W is:\n')

N=size(w);

for i=1:N(1) %Function to display the basis of the row space of W

fprintf('(%2d',w(i,1));

for j=2:N(2)

fprintf('%4d',w(i,j));

end

fprintf(')\n');

end

fprintf('A basis for U+W is:\n')

N=size(f);

for i=1:N(1) %Function to display the basis of the row space of U+W

fprintf('(%2d',f(i,1));

for j=2:N(2)

fprintf('%4d',f(i,j));

end

fprintf(')\n');

end

fprintf('A basis for the intersection of U and W is:\n')

N=size(R);

for i=1:N(1) % %Function to display the basis of the row space for the intersection of U and W

fprintf('(%2d',R(i,1));

for j=2:N(2)

fprintf('%4d',R(i,j));

end

fprintf(')\n');

end

Program rank2

function f=rank2(a,p)

b=echelon(a,p); %Function to turn the matrix into echelon form

rowspace = [];

d =size(a);

g=sum(b');

for i=1:d(1) %Function to collect the basis of the row space

if g(i)~=0

rowspace = [(rowspace);(b(i,:))];

end

end

f=rowspace;

Program kernel2

function f=kernel2(a,p)

% This function finds the basis of the kernel of matrix a

% p is such that a*mod(p)

E=echelon(a,p);

r=rank1(a,p);

clc

N=size(a);

U=zeros(N(2)-r,N(2));

i=1;

d=1;

for j=1:N(2) %Function used to find l(k)=j

if i<=N(1) && E(i,j)==1

l(i)=j;

i=i+1;

else %Function used to form the initial matrix U of the kernel

U(d,j)=1;

d=d+1;

end

end

for i=1:N(2)-r

for k=r:-1:1

for j=l(k)+1:N(2)

U(i,l(k))=U(i,l(k))-E(k,j)*U(i,j);

U(i,l(k))=mod(U(i,l(k)),p);

end

end

end

f=U(:,:);

 

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!