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

Similar to Lemma 1 we can restrict ourselves to the case thatM T is the
multiset that consists of all column permutations of a matrix MT. T .
For S f1;:::;ng we denote by x T S the number of columns of MT T that
have a 1 in the rows i 2 S and a zero in the rows i 2 S. The number of
black subpixels in the image I S is either h S (when a black pixel is encoded) or
l s when a white pixel is encoded. Analog to the linear program for ordinary
visual cryptography we get

Mx T = r T (8.27)
where r T = (r T S ) ;6=Sf1;:::;ng with r T S = h S if S 2Tand r T S = l S if S 2T.
The (2 n 1) (2 n 1) matrix M = (m S;T ) ;6=S;Tf1;:::;ng is defined by
m S;T = 1 if S \T 6= ; and m S;T = 0 otherwise.
It possible to solve the program explicitly and the starting point is the
observation that M has an simple inverse.

Lemma 18 The matrix M = (m S;T ) ;6=S;Tf1;:::;ng with m S;T = 1 if S\T 6= ;
and m S;T = 0 otherwise is invertible and M 1 has only the entries 1 and 0.

Proof
We prove this by induction on the number n of transparencies.
Sort the variables xT T by the following order: First, we enumerate all subsets
that do not contain n. The next subset is the set fng. Then, the other subsets
containing n follow.
Writing M 1 = (1), we obtain the following recursion formula that follows
directly from the definition:

0 1

M n 0 n;1 M n
0 1;n

@ A :

M n+1 = 1 1 1;n

M n 1 n;1 1 n;n

Here the index denotes the number of transparencies. 0 i;j or 1 i;j , respectively,
denoting a (2 i 1) (2 j 1) matrix with all entries 0 or 1, respectively.
With M 1
1

= (1) we obtain the following recursion formula for M n :

0 1

M n 1 n;1 M 1

n

0 n;n

@ A

M 1 1 1;n M 1 1 1;n M 1

n+1 =

0

n n

M 1
n

M n 1 n;1 M 1

n

Thus, M is invertible, i.e., Equation (8.27) has a unique solution.
We notice that the components of M n 1 n;1 are only 1; 0, and 1 and that
1 1;n M n 1 n;1 = 1. Then the formula can be proved by induction.
Thus, M n contains only the entries 1; 0, and 1 and therefore the solution
of equation (8.27) is integral.

2
By Lemma 18 the solution xT T of equation (8.27) is an integer vector if the
right-hand side rT T is an integer vector.