I'm preparing for a Computer Science interview at Cambridge and I came across this question:
With a rectangular table of binary digits it is always possible to add an extra row and an extra column so that every row and every column of the resulting table has an even number of ones and zeros in it. Explain why. Is it always possible to add a row and column to a table of binary digits where every row and every column of the resulting table has an odd number of binary digits?
This is the answer:
Parity Matrix
Adding respectively an extra row or column to a table so that the parity of all columns or rows respectively is odd or even is always straightforward. Adding both at once adds one extra cell that is overspecified (at the intersection of extra column and row – at bottom right hand corner if we extend in length and to the right).
The overspecification is not a conflict with even parity. This can be seen by considering every possible original table as a sum of a certain number of tables each with a single one in it and noting that addition of tables (using cell-by-cell xor) preserves even parity. Infact, it is soon clear that the conflicted cell is always clear.
The overspecification is not a conflict with odd parity for certain table sizes. Another argument that works for even parity is based on the whether the tally of the unextended table is odd or even. The associativity of addition means that the same digit is required in the corner cell for even parity however you perform the tally. However, for odd parity, a virtual r or c additional ones have been summed, where r and c are the number of rows and columns in the original table. There is no conflict if r and c have the same parity.
I can't understand the question or the answer.
If we have the following table:
╔═════════════╗ ║ 1 0 0 0 1 1 ║ ║ 1 0 0 0 1 1 ║ ║ 1 0 0 0 1 1 ║ ║ 0 1 1 1 0 0 ║ ║ 0 1 1 1 0 0 ║ ║ 0 1 1 1 0 0 ║ ╚═════════════╝
How can we add an extra row and an extra column so that every row and every column of the resulting table has an even number of ones and zeros in it? Also, what exactly does the answer mean by "parity" (I'm vaguely familiar with it, but I'd like some more info) and how does it relate to the question?
Thanks in advance.
Edit: The question is found here.
Best Answer
I think you are justifiably confused. This is a poorly worded question and an obscure answer.
Let's start with the question. The main problem is the vagueness of this phrase:
What does "even number of ones and zeros" mean? It can mean any of these things:
1sis even, and also the number of0sis even1s+ the number of0s) is evenAfter I thought about it, I realised that none of these options make much sense with the question posed. They all make the opening statement/claim false (even though the question asks us to prove why it is true). It turns out that the question does not mean any of these options but instead means:
Or in other words, if we add all the digits of a row or a column (of the extended table) we will get an even number. This is made clearer in the answer, where the parity of rows and columns is mentioned. Parity, in general, means whether an integer is even or odd. If we are talking about the parity of a string of bits (as in our case) then parity refers to the parity of the sum of the bits, or in other words whether the number of
1sin the string is even or odd. In computer science, we have the parity bit which is a bit added to a string of bits in order to always make the parity of the (extended) string be even. So in essense this question asks about adding an extra row and an extra column of parity bits.Also note that the ending question which mentions
is clearly wrong. They mean to say:
The crux of the question
Let's look into the heart of the question. What is the problem here? If I give you a string of bits, it's easy to compute the (even) parity bit. You count the
1sand if they are even the parity bit is $0$, otherwise we set it to $1$. Here are the parity bits (in blue) for every row and column of your example table:$$ \begin{array}{llllll|l} 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ \hline \color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}& \color{red}? \end{array} $$
They all happen to be $1$ with the table example you gave. The real problem is: What is the bit denoted as a red questionmark? This bit should set the even parity for both the extra row and the extra column. In other words, it is the parity bit of the column of parity bits, as well as the parity bit of the row of parity bits. Since just a single string of bits (either a row or a column) can fully specify a parity bit, our red questionmark bit is overspecified. In our example above we can set it to $\color{red}0$ and satisfy both the extra row and column (i.e., we can set it with no conflict).
Let's see another table. Just take our previous example table and make it non-square by removing the last row. So now we have:
$$ \begin{array}{llllll|l} 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ \hline \color{blue}{1}&\color{blue}{0}&\color{blue}{0}&\color{blue}{0}&\color{blue}{1}&\color{blue}{1}& \color{red}1 \end{array} $$
Again we find that the overspecified bit satisfies the even parity of both the extra row and the extra column. Is this always the case? The question claims that it is, and we need to explain why.
The answer
The first observation I made was that if we change a single bit in the $6\times 6$ table of our example (or the truncated $5\times 6$ table), a single bit in the parity column will change, and a single bit in the parity row will also change. This means that the overspecified bit will change too, and both parity row and parity column will be in agreement. So any number of bit changes we make for these table sizes will be ok (no conflict for the overspecified bit). But is there some other table size that produces a conflicted overspecified bit? We could perhaps make an inductive proof for every size table starting with a $1\times 1$ table, but there is a simpler method:
I made this general observation about even parity:
This might sound a bit confusing, so let me write it with symbols in order to make it more digestable. I will use the following notation: If $S$ is a string of bits, then $P_e(S)$ is the even parity bit of this string. Also if $S_1, S_2$ are bitstrings, then $S_1\oplus S_2$ is the concatenation of these two strings (in other words "glue" them together to make a bigger string). Finally a parity bit can be considererd a bitstring of length one and can be concatenated with other strings. This is what I claim:
$$P_e(S_1\oplus S_2) = P_e(P_e(S_1)\oplus P_e(S_2))$$
To prove this claim simply consider all four combinations of parity for two strings:
(odd, odd),(even, odd),(odd, even),(even, even). Note that when we concatenate two odd strings we get one even string, when we concatenate one odd and one even we get odd, and finally two even strings concatenate in one even. Let $O$ denote odd strings and $E$ denote even strings in the formulas below.$$ \begin{array}{rlrlrl} P_e(O\oplus O)&= P_e(P_e(O)\oplus P_e(O)) &\iff P_e(E) &= P_e(1\oplus 1)) &\iff 0&=0 \\ P_e(O\oplus E)&= P_e(P_e(O)\oplus P_e(E)) &\iff P_e(O) &= P_e(1\oplus 0)) &\iff 1&=1 \\ P_e(E\oplus O)&= P_e(P_e(E)\oplus P_e(O)) &\iff P_e(O) &= P_e(0\oplus 1)) &\iff 1&=1 \\ P_e(E\oplus E)&= P_e(P_e(E)\oplus P_e(E)) &\iff P_e(E) &= P_e(0\oplus 0)) &\iff 0&=0 \end{array} $$
And more generally: $$P_e(S_1\oplus S_2\oplus \dots \oplus S_n) = P_e(P_e(S_1)\oplus P_e(S_2)\oplus \dots \oplus P_e(S_n)) \qquad (\text{lemma}\; 1)$$
The generalisation is actually crucial for what we want to prove. I will not give a full proof here, but instead provide a sketch and leave the fleshed out proof as an exercise. To prove lemma 1 we need to consider having $i$ odd strings and $k$ even strings. Then examine all four cases were $i,k$ are
(odd, odd),(even, odd),(odd, even),(even, even).After we have established lemma 1, notice again that the overspecified bit is the even parity of the bits in the parity column. In turn, the bits in the parity column are the even parities of the rows of the table. So, using lemma 1, we can say that the overspecified bit is the even parity bit of all the bits in the table. If this is unclear just set strings $S_1,\dots S_n$ in lemma 1 to be the rows of bits of our table. Moreover, we can have the same argument about the overspecified bit being the parity of the bits in the parity row, and again we end up with the overspecified bit being equal to the parity of all bits in the table (this time we set strings $S_1,\dots S_n$ in lemma 1 to be the columns of bits of our table). In other words, it does not matter if we consider all the bits row-first, or column-first, the overspecified bit is essentially calculated as the even parity bit of all bits in the table. In a picture:
$\hspace{2cm}$
Saying the same thing with formulas: Let $R_1, R_2,\dots R_n$ be the rows of the original (non-extended) table of bits. And let $C_1, C_2,\dots C_n$ be the columns. We have:
$$ P_e(P_e(R_1)\oplus P_e(R_2)\oplus \dots \oplus P_e(R_n)) \stackrel{\text{lemma 1}}= P_e(R_1\oplus R_2\oplus \dots \oplus R_n) = P_e(\text{all the bits in the table}) = P_e(C_1\oplus C_2\oplus \dots \oplus C_n) \stackrel{\text{lemma 1}}= P_e(P_e(C_1)\oplus P_e(C_2)\oplus \dots \oplus P_e(C_n)) $$
Their answer
I believe that the answer given on the webpage is playing with properties closer to my first observation. The problem is that it describes the "solution" with very few words ("addition of tables (using cell-by-cell xor) preserves even parity") and ends up being obscure. When I first read it, I had no idea what it meant. Now that I've done my analysis I think I understands what it means.
I believe that the general idea is to break the table into "basic" tables where only one cell has a
1and then you add the parity row and column for each of them to get an extended "basic" table. The parity row and column of an extended "basic" table have only one1bit each, and the overspecified bit is always1. Then you combine these extended basic tables by doing bitwise XOR operations and it is implied that you get your initial extended table. It is further implied that there will always be a valid oversimplified bit. Even though all this is correct, it needs considerably more work to be proven and explained properly. It seems to me that this solution gets messy when you try to explain it properly. I prefer my approach, as I think it's cleaner, but that's a matter of taste.An odd parity matrix
The question finally asks us what happens if we choose odd parity. Can we always have a valid overspecified bit? It seems that it is nudging us towards a "no". It's easy to find a counterexample. Just look at the truncated table we used before. Let's consider the odd parities this time: $$ \begin{array}{llllll|c} 1& 0& 0& 0& 1& 1& \color{blue}0\\ 1& 0& 0& 0& 1& 1& \color{blue}0\\ 1& 0& 0& 0& 1& 1& \color{blue}0\\ 0& 1& 1& 1& 0& 0& \color{blue}0\\ 0& 1& 1& 1& 0& 0& \color{blue}0\\ \hline \color{blue}{0}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&\color{blue}{0}& \color{red}{0/1} \end{array} $$
We see that now the overspecified bit is conflicted. We could stop there as far as the question is concerned (we found a counterexample) but thanks to our earlier analysis we know why this is the case: Odd parity does not have the property that even parity has. More specifically:
$$P_o(S_1\oplus S_2\oplus \dots \oplus S_n) \neq P_o(P_o(S_1)\oplus P_o(S_2)\oplus \dots \oplus P_o(S_n))$$
For example, consider three odd-parity strings: $$P_o(O\oplus O \oplus O) \neq P_o(P_o(O)\oplus P_o(O) \oplus P_o(O)) \iff P_o(O) \neq P_o(0\oplus 0 \oplus 0)) \iff 0 \neq 1$$
I hope you now have a much fuller understanding of the question and the answer. It was certainly rewarding for me to investigate it.