Start by proving that in the square matrix (like the one, shown in the table in the problem statement), the diagonal elements are always 0's if the first bit of the bitstring is 0.