Algorithm for construction tournament matrix

Question

The $(0,1)$ matrix $A=\left[a_{i,j}\right]$ is a tournament matrix if we have: $a_{i,i}=0$ and $a_{i,j}=1-a_{j,i}$ for $i \neq j$. Is there any algorithm for construction an $n \times n$ tournament matrix with $R=(r_{1},r_{2},\ldots,r_{n}), r_{i}=(n-1)/2$, where $r_{i}$ is the sum of the elements of the ith row of $A$?

Thanks in advance.

Answer 1

Since $A$ has elements in $\{0,1\}$ it is necessary that $n$ is odd. The following algorithm will assign the elements of $A$ to produce the desired structure. Initially, let $a_{11} = 0$, let $a_{1j} = j\!\!\!\mod\!\!2$ (or $(j+1)\!\!\!\mod\!\!2$) for $j = 2,\ldots,n$ and let $a_{j1} = 1 - a_{1j}$. For the second row let $a_{22} = 0$, $a_{2j} = 1 - a_{1j}$, and $a_{j2} = 1 - a_{2j} = a_{1j}$ for $j = 3,\ldots,n$. In general for row $i$ let $a_{ii} = 0$, $a_{ij} = 1 - a_{i-1,j}$, and $a_{ji} = a_{i-1,j}$ for $j = i+1,\ldots,n$. Repeat this procedure iteratively until all that is left is to assign $a_{nn} = 0$.

Clearly the matrix $A$ has the desired structure by construction. To show that each row of $A$ sums to $(n-1)/2$ it is enough to observe that the $i$th row is obtained by "rotating" the $(i-1)$th row one element to the right, for $i = 2,\ldots,n$. Since $r_1 = (n-1)/2$ and rotating a row does not change its sum, it follows that all rows of $A$ sum to $(n-1)/2$. A similar argument shows that each column of $A$ sums to $(n-1)/2$ as well.

Let A be an n by n matrix of zeros
for j = 2,...,n
    if j is even
        A(1,j) = 1
    else
        A(j,1) = 1
    end
end
for i = 2,...,n
    for j = i+1,...,n
         A(i,j) = 1 - A(i-1,j)
         A(j,i) = A(i-1,j)
    end
end