×

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
PDF BibTeX XML Cite