zbMATH — the first resource for mathematics

Testing of random matrices. (English) Zbl 1244.68089
Summary: Let $$n$$ be a positive integer and $$X=[x_{ij}]_{1\leq i,j\leq n}$$ be an $$n\times n$$ sized matrix of independent random variables having joint uniform distribution $\text{Pr}\{x_{ij}=k\text{ for }1\leq k\leq n\}=\frac {1}{n}\quad (1\leq i,j\leq n).$ A realization $${\mathcal M}=[m_{ij}]$$ of $$X$$ is called good, if its each row and each column contains a permutation of the numbers $$1,2,\dots,n$$. We present and analyse four typical algorithms which decide whether a given realization is good.
MSC:
 68W30 Symbolic computation and algebraic computation 05B15 Orthogonal arrays, Latin squares, Room squares 68W40 Analysis of algorithms