The discrete Wigner distribution (WD) encodes information in a redundant fashion since it derives N by N representations from N-sample signals. The increased amount of data often prohibits its effective use in applications such as signal detection, parameter estimation, and pattern recognition. As a consequence, it is of great interest to study the redundancy of information it carries. Richard and Lengelle (see Proc. IEEE Int.Conf. Acost., Speech, Signal Process., Istanbul, Turkey, p.85-8, 2000) have shown that linear relations connect the time-frequency samples of the discrete WD. However, up until now, such a redundancy has still not been algebraically characterized. In this paper, the problem of the redundancy of information carried by the discrete cross WD of complex-valued signals is addressed. We show that every discrete WD can be fully recovered from a small number of its samples via a linear map. The analytical expression of this linear map is derived. Special cases of the auto WD of complex-valued signals and real-valued signals are considered. The results are illustrated by means of computer simulations, and some extensions are pointed out.