Visual Cryptography and Contrast Bounds - Visual Cryptography and Secret Image Sharing - page 230

Proof
Let M B be the matrix describing the encoding of a black pixel. As in the proof
of Theorem 8 we find that each transparency must have the same number w
of black subpixels and each two transparencies must share the same number
< w of black subpixels. Interpret M B as an integer matrix, then
M B M B = (w)I + J :
This matrix has a full rank (det(w)I +J = (w) n1 (n+w)) and
hence,

4n 1 = rank M B M B rank M B m :
(This is the Fisher's inequality.)
Now assume m = 4n 3 then w must be either 2n 1 or 2n. In the
first case every column of M W must contain 2n 1 entries 1 and M W is the
incidence matrix of a 2(4n1; 2n1;n1) design. In the second case every
column of M W must contain 2n entries 1 and M W is the incidence matrix of
a 2(4n1; 2n;n) design. But then the complement of M W is the incidence
matrix of a 2 (4n 1; 2n 1;n 1) design. This shows that a contrast
optimal 2-out-of-(4n 1) visual cryptography scheme with pixel expansion
m = 4n 3 implies the existence of a 2 (4n 1; 2n 1;n 1) design.
But conversely you get a 2-out-of-(4n 1) visual cryptography scheme from
a 2(4n1; 2n1;n1) design by dening M B to be the incidence matrix
of the design and encode it with a pixel by choosing on all transparencies the
same subpixels.
Now we prove that the existence of 2 (4n 1; 2n 1;n 1) design is
equivalent to the existence of a Hadamard matrix of order 4n.
Multiplying a row or a column of a Hadamard matrix with 1 again gives
a Hadamard matrix. So without loss of generality we may assume that the
first row and the first column of a Hadamard matrix has only 1 as entries. Let
H be a Hadamard matrix of order 4n in that normal from. All rows except
the rst row of H must contain 2n entries 1 and for two rows dierent rows
must differ in exactly 2n columns. Hence, after deleting the first row and first
column H forms the incidence matrix of a 2 (4n 1; 2n 1;n 1) design
(with 1 instead of 0 to mark that a point is not incident with a block).
Conversely the incidence matrix of a 2 (4n 1; 2n 1;n 1) becomes a
Hadamard matrix, if one replaces all 0 by 1 and adds an extra column and
an extra row that contains only 1.

2
Other 2-out-of-n visual cryptography schemes are also connected to
Hadamard matrices.

Result 11 (see [3] Theorem 4.9) The minimal pixel expansion m of con-
trast optimal 2-out-of-n visual cryptography schemes satisfies:

8
<

2n 2 if n even

m n if n 3 mod 4

:

2n if n 1 mod 4