1
$\begingroup$

I have studied that for orthogonality to exist between two binary sequences:
[Number of bit agreements - Number of bit disagreements]/sequence length=0

Eg, for an orthogonal matrix X given by:

\begin{bmatrix}0&0&0&0\\0&1&0&1\\0&0&1&1\\0&1&1&0\end{bmatrix}
Any two rows satisfy the rule above, showing that any two binary sequences defined by two different rows of X are orthogonal.


However, if we consider the case of Generator(G) and Parity Check(H) Matrix, the rows of G are orthogonal to rows of H. But the rule stated above, doesn't prove it. Why so?

1) How do we verify that two binary sequences are orthogonal?
2) Can we extend the same testing rule to check orthogonality between the rows of two matrices?


Example:

G =\begin{bmatrix}1&1&0&1&0&0\\0&1&1&0&1&0\\1&0&1&0&0&1\end{bmatrix}
and H = \begin{bmatrix}1&0&0&1&0&1\\0&1&0&1&1&0\\0&0&1&0&1&1\end{bmatrix}
These two matrices claim to have orthogonal rows . So, if we take (let's say) first row of G and H and apply the formula I mentioned, why don't they give 0?

They do give 0 by modulo 2 addition of the product of two rows, but why the formula that I mentioned, is not applicable?


$\endgroup$
6
  • 1
    $\begingroup$ I think your first equation holds only if you take your bits to be $\pm1$, rather than zero and one. $\endgroup$ Aug 5, 2015 at 7:27
  • $\begingroup$ you are absolutely right. But the thing is, even when bits are taken in ±1 form, the above equation doesn't hold for orthogonal rows of G and H matices. $\endgroup$ Aug 5, 2015 at 8:29
  • $\begingroup$ For the first formula, we are talking about orthogonality over the reals. For the matrices, we are talking about orthogonality over the field of two elements. What's orthogonal in one setting needn't be so in the other. $\endgroup$ Aug 5, 2015 at 9:06
  • $\begingroup$ I have edited my question to make it as clear as possible. $\endgroup$ Aug 5, 2015 at 9:49
  • $\begingroup$ There was nothing unclear about the original statement. Your matrix $X$ is not orthogonal. If you replace the zeros with minus ones, then it becomes orthogonal. Your matrices $G#$ and $H$ are orthogonal, but over the field of two elements, not over the reals. $\endgroup$ Aug 5, 2015 at 13:21

1 Answer 1

0
$\begingroup$

For binary vectors to be orthogonal, you are taking the normal dot product, and adding $\bmod{2}$. So they have to agree in "1" an even number of times to be orthogonal.

Each nonzero vector represents a 1-dimensional subspace of $\mathbb{F}_{2}^{k}$. If $v \neq 0$, then $v^{\perp}$ will be a subspace of $\mathbb{F}_{2}^{k}$ with dimension $k-1$. Think of the vector $[0,0,1]$ in $\mathbb{F}_{2}^{3}$: it is orthogonal to $\{[0,0,0], [1,0,0], [0,1,0], [1,1,0]\}$. This is the hyperplane satisfying $x_{3} = 0$. This is similar to standard orthogonality, where $v^{\perp}$ in $\mathbb{R}^{k}$ will have dimension $k-1$.

I think your formula involves representing binary vectors as 1/-1 vectors, and orthogonality being over $\mathbb{R}$ in the usual sense.

$\endgroup$
3
  • $\begingroup$ Yes, but the thing is: is this way ( taking the normal dot product, and adding mod2 ) the right way? If it is, it would mean that [0000] and [0001] are also orthogonal, which looks strange... $\endgroup$ Aug 5, 2015 at 11:26
  • $\begingroup$ It means that every two vectors, with even "1" agreements, are orthogonal over binary field? So, if we have a set of (2^k)-1 non-zero vectors of same length k bits , any particular element of the set will be orthogonal(uncorrelated) to half of the set elements(as mod 2 addition of product will give 0), and parallel(100% correlated) to other half, as mod 2 addition of product will give 1. --------------------- eg: any element of the set {[001], [010], [011],[100],[101],[110],[111]} is orthogonal to half of the elements and parallel to other half. Am I right? $\endgroup$ Aug 5, 2015 at 12:18
  • $\begingroup$ Thanks a lot sir :) You saved my day $\endgroup$ Aug 5, 2015 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .