Can anyone tell me how to generate a binary orthogonal complement of a given binary matrix ??

I have been given a certain binary matrix of (K X N) dimension.

the matrix is S=

s =

[ 0 0 0 0 0 1 0 1 0 0 0 0;

0 0 0 1 0 0 0 0 1 0 0 0;

0 0 0 0 1 0 1 0 0 0 0 0;

1 0 0 1 0 0 0 0 1 0 1 0;

0 1 0 0 1 0 1 0 0 0 0 1;

0 0 1 0 0 1 0 1 0 1 0 0]

I need to find the binary orthogonal complement of S.

Answer 1

[Bruno Luong]

I'm not expert of calculation in finit field, so just use brute force, there are 63 vectors that are orthogonal to the s you provide

s =[ 0    0    0    0    0    1    0    1    0    0    0     0;
    0    0    0    1    0    0    0    0    1    0    0     0;
    0    0    0    0    1    0    1    0    0    0    0     0;
    1    0    0    1    0    0    0    0    1    0    1     0;
    0    1    0    0    1    0    1    0    0    0    0     1;
    0    0    1    0    0    1    0    1    0    1    0     0]

s = 6×12

0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0

B=(dec2bin(1:2^size(s,2)-1)-'0')';
k=find(all(mod(s*B,2)==0,1));
t = B(:,k)

t = 12×63

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1

[saydur rahman]

can you describe it how you compute the matrix? is the t is orthgonal complement to S? then inner product of <S,t> should be zero or S'.t==0.

[Torsten]

then inner product of <S,t> should be zero or S'.t==0.

I think S*t = 0 (mod 2), isn't it ?

At least testing with all possible binary vectors t shows that S*t = 0 is not possible for any binary t.

[saydur rahman]

but orthogonal complement needs to be inner product or (S^T * t) needs to be zero, right??

[Torsten]

What is the underlying field for the vector space you consider ? Is it IR or Z_2 ? If it's IR, you don't need to consider binary vectors for the orthogonal complement, you you can just use Gram-Schmidt. So I guess it's Z_2. And in this case, you get the 63 vectors from above. Now it's up to you to sort out a basis.

[saydur rahman]

the t needs to be binary . i think the inner product of two orthogonal complement matrix should be zero. if i chose t is the orthogonal complement basis and select any of the 6 form that, then multiplication of S^T(transpose of S) and t should be zero .

[Torsten]

t is in the orthogonal complement of s if s*t = 0 (modulo 2).

This is true for all the 63 columns of t from above.

To get a basis of the orthogonal complement of s, you will have to check how many of the 6 rows of s are linear independent. If these are k <= 6, you will have to find 12 - k out of the 63 from the matrix t that are also linear independent.

Keep in mind that s*t = 0 means 0 modulo 2, not the "usual" 0. Thus results like 2, 4, 6,... for the entries of s*t are 0 (modulo 2).