Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to calculate rank over $GF(2)$ of a matrix. I understand what rank of a matrix is but I have no idea what rank over $GF(2)$ means or how to compute it. Google is not helping.

What is rank over $GF(2)$?

It will be very helpful if you explain it with a concrete example.

NOTE: I am not looking for efficient algorithm to do this. I want to learn to do this by hand and understand the concept in general.

I am trying to solve problem 1.1.15 from Graph Theory book by Bondy and Murthy.

Thanks!

share|improve this question
    
what does GF(2) represent? –  Shiyu Apr 20 '11 at 10:47
    
Galois Field of 2 elements. –  Pratik Deoghare Apr 20 '11 at 10:49
add comment

3 Answers

up vote 2 down vote accepted

GF(2) stands for "Galois Field with 2 Elements". It is an example of a finite field:

http://en.wikipedia.org/wiki/Finite_field

You are probably used to using the real numbers as your scalars when you work with matrices (so entries are real and scalar multiplication is by real numbers). It turns out that most or all of the matrix theory you know is valid when you allow scalars from certain other algebraic structures, called "fields". A field is a set with two operations, addition and multiplication, which have all of the nice properties of addition and multiplication that the real numbers have. See

http://en.wikipedia.org/wiki/Field_(mathematics)

for more specifics. In particular, since you can add and multiply elements in a field, then matrices whose entries are drawn from the field can be added and multiplied using the same algorithms you already know.

So...a field is a set with two operations satisfying a bunch of nice properties. Which set is GF(2)? It has 2 elements: {0, 1}. The rules for addition and multiplication are exactly the same as if 0 and 1 were the usual real numbers 0 and 1 (so that 0 times anything is 0, for example), with one exception: since there is no "2" in the set, we define "1+1=0".

To find the rank of a matrix, you can calculate the dimension of the row space with Gaussian elimination. Just remember that the entries are all 0's and 1's with the operations I just described, so for instance to eliminate some 1's below a leading 1, you can simply add rows together since the leading 1's will add to 0 with the operations in GF(2).

One word of caution: it is possible for vectors of 0's and 1's to be independent when considered as vectors with real number entries, but dependent when considered to have entries in GF(2). But if you reduce your matrix to row-echelon form to determine the dimension of the row space, this phenomenon will not arise in that particular case.

share|improve this answer
add comment

The rank is equivalently the dimension of the row space of the matrix (the space spanned by its row vectors), the dimension of the column space of the matrix, and the dimension of the image of the linear map between vector spaces (with specified bases) represented by the matrix. You can calculate the dimension of the row space just as you would for any other field (e.g. $\mathbb{R}$) by bringing the matrix into row echelon form using Gaussian elimination. Since the only non-zero element in this case is $1$, you don't need any multiplications; just pick any $1$ as pivot, then cancel all the other $1$s in the column below it.

share|improve this answer
    
but what is significance of $GF(2)$ in this case? –  Pratik Deoghare Apr 20 '11 at 10:53
    
I'm not sure I understand the question. The only way I can make sense of the question is if you're thinking of treating the $0$ and $1$ as real numbers and considering "rank over $GF(2)$" merely as a restriction that all entries are either $0$ or $1$. The meaning of "rank over $GF(2)$" is that all operations are to be performed within $GF(2)$, that is, if you add a $1$ to a $1$, you get a $0$. Does that answer your question? –  joriki Apr 20 '11 at 10:56
    
Ok. So if I follow multiplication and addition tables for $GF(2)$ given on wikipedia and do usual rank calculations will it be fine? –  Pratik Deoghare Apr 20 '11 at 10:59
    
That's exactly right. Sorry I misunderstood your question at first. –  joriki Apr 20 '11 at 11:00
    
Thank you @joriki !! :) –  Pratik Deoghare Apr 20 '11 at 11:01
add comment

Rank of a matrix in GF(2) cannot be obtained using rudimentary ways in R. You have to use row elimination and performe all of the operations in Modulo 2. As we know rank of A and transpose(A)*A and A*tranpose(A) are all the same but in GF(2) the table turns. Let me exemplify by a matrix :

A =

 1     0     0     1     0     1

 0     1     0     1     1     1

 0     0     1     1     1     0

as you can easily check the rank is 3 ( both in R and GF(2) )

A*transpose(A) is

 3     2     1                            1 0 1 
 2     4     2    which in GF(2) becomes  0 0 0
 1     2     3                            1 0 1  

which has rank 1 !!!!!

Moreover , as I said earlier rank in R is not the same as rank is GF(2). look at the following example :

A =

 1     1     0

 0     1     1

 1     0     1

rank of this matrix is 3 but as you can see in GF(2) the 3rd row is row 1 + row 2 ( notice that the addition here is in Modulo 2 ).

So the best way to calculate the rank is elementary row operations which is carried out in GF(2).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.