I've 13 rows in a matrix, which are linearly independent.(number of columns is 20), in GF(2). Now i have to find 20 orthogonal vectors in GF(2). I've added 20 more rows which are the rows of an identity matrix, to find them. Gram schmidt process fails here.
How to find the orthogonal vectors?
Regards, phani tej
On
As others have pointed out Gram-Schmidt will not work over $GF(2)$. As you tagged the question with coding-theory I will point out that so called self-dual codes are a most striking example of this. The space $V=GF(2)^{n}$, $n$ even, has certain subspaces $W$ of dimension $n$ such that all the vectors in $W$ are orthogonal to all the vectors in $V$ (including orthogonal to themselves). This is because over $GF(2)$ we have no useful notion of positive elements, and cannot relate length and inner-product the same way we do in $\Bbb{R}^n$.
An example of such a subspace $W$ in the case $n=4$ is the row space of the matrix $$ G=\left(\begin{array}{c}1100\\0011\end{array}\right). $$ Both rows of $G$ are orthogonal to themselves and each other.
What does hold (and I somehow suspect that you are really asking about this but did not quite formulate it that way) is the following (proof is pretty standard linear algebra). I denote the "inner product" of two vectors, $u,v,$ from $GF(2)^n$ by $\langle u,v\rangle$.
Proposition. Let $V=GF(2)^n$, and let $W$ be a $k$-dimensional subspace of $V$. Then the set $$ W^\perp=\{x\in V\mid \langle x,y\rangle=0\ \text{for all $y\in W$}\} $$ is also a subspace of $V$. Furthermore, it is of the complementary dimension $n-k$, so $$ \dim V=\dim W+\dim W^\perp. $$
The proof of this proposition only needs the fact that the inner product is non-degenerate, i.e. no vector is orthogonal to all the vectors.
In coding theory you have probably seen this result in the form that to every binary linear code $C$ (= the row space of its generator matrix $G$) we also have a parity check matrix $H$ (= a generator matrix of the dual code $C^\perp$). So in the case of a self-dual code we have $C=C^\perp$.
Finding $H$ given $G$ is easy. Judging from your earlier question you have seen the rule that can be applied when $G$ is systematic, i.e. of the form $G=(I|P)$, where $I$ is the $k\times k$ identity block and $P$ is some $k\times(n-k)$ matrix. If $C$ is the row space of $G$, then the dual code $C^\perp$ is the row space of the $(n-k)\times n$ matrix $$ H=(P^T|I), $$ this time with an $(n-k)\times (n-k)$ identity block. Notice that going from a code to its dual is a two-way street. Given $H$ in the above form we can easily revert the process to get a generator matrix.
Unfortunately not all the linear codes have systematic generator matrices (unless you are willing to permute the bit positions). A well known example is the Hamming code of length seven. It is often defined using a check matrix $$ H=\left(\begin{array}{c}1010101\\0110011\\0001111\end{array}\right). $$ Because the first three columns of this matrix are linearly dependent no sequence of row operations can bring it to the systematic form $(I_3|P)$.
But this does not change the validity of the above proposition! Observe that columns 1,2 and 4 of $H$ do form an identity block. An exercise in linear algebra tells us that as long as the $k\times n$ matrix $G$ has full rank $k$, then a sequence of row operations will put in the form where some $k$ columns form an identity block. Those columns are marked by the "leading ones" of the said matrix in its reduced row-echelon form. The usual trick $(I|P)\leftrightarrow (P^T|I)$ works even if the columns of the $I$ block are not all in the beginning. We simply need to put that transpose $P^T$ on the same set of columns. In the case of the Hamming code we have (from columns 3,5,6 and 7 of $H$) $$ P=\left(\begin{array}{c}1101\\1011\\0111\end{array}\right). $$ If we put $P^T$ into columns 1,2,4 (and fill columns 3,5,6,7 with columns of $I_4$) we get the matrix $$ G=\left(\begin{array}{c}1110000\\1001100\\0101010\\1101001\end{array}\right). $$ Observe that the rows of $P$ appear as columns of $G$.
I invite you to check that all the rows of $G$ are orthogonal to all the rows of $H$. Hence each of them can take the role of the parity check matrix for the code generated by the other.
In general, it's impossible to orthogonalize sets of vectors over $GF(2)$. For example, take the subspace of $GF(2)^3$ orthogonal to $(1,1,1)$. That two-dimensional subspace consists of the four vectors $(0,0,0)$, $(1,1,0)$, $(1,0,1)$, and $(0,1,1)$; no two of those vectors form an orthogonal basis for the subspace. Similar problems occur in higher dimensions (just pad those vectors with $0$s). So in general there's no way to make Gram-Schmidt work over $GF(2)$.