Weighing matrix

Weighing matrices are so called because of their use in optimally measuring the individual weights of multiple objects

In mathematics, a weighing matrix of order $n$ and weight $w$ is a matrix $W$ with entries from the set $\{0,1,-1\}$ such that:

$WW^{\mathsf {T}}=wI_{n}$

Where $W^{\mathsf {T}}$ is the transpose of $W$ and $I_{n}$ is the identity matrix of order $n$. The weight $w$ is also called the degree of the matrix. For convenience, a weighing matrix of order $n$ and weight $w$ is often denoted by $W(n,w)$.

Weighing matrices are so called because of their use in optimally measuring the individual weights of multiple objects. When the weighing device is a balance scale, the statistical variance of the measurement can be minimized by weighing multiple objects at once, with some in the opposite pan where they are subtracting from the measurement.

Properties

Some properties are immediate from the definition. If $W$ is a $W(n,w)$, then:

• The rows of $W$ are pairwise orthogonal (that is, every pair of rows you pick from $W$ will be orthogonal). Similarly, the columns are pairwise orthogonal.
• Each row and each column of $W$ has exactly $w$ non-zero elements.
• $W^{\mathsf {T}}W=wI$, since the definition means that $W^{-1}=w^{-1}W^{\mathsf {T}}$, where $W^{-1}$ is the inverse of $W$.
• $\det(W)=\pm w^{n/2}$ where $\det(W)$ is the determinant of $W$.

A weighing matrix is a generalization of Hadamard matrix, which does not allow zero entries. As two special cases, a $W(n,n)$ is a Hadamard matrix and a $W(n,n-1)$ is equivalent to a conference matrix.

Applications

Experiment design

See also: Design of experiments § Example

Weighing matrices take their name from the problem of measuring the weight of multiple objects. If a measuring device has a statistical variance of $\sigma ^{2}$, then measuring the weights of $N$ objects and subtracting the (equally imprecise) tare weight will result in a final measurement with a variance of $2\sigma ^{2}$. It is possible to increase the accuracy of the estimated weights by measuring different subsets of the objects, especially when using a balance scale where objects can be put on the opposite measuring pan where they subtract their weight from the measurement.

An order $n$ matrix $W$ can be used to represent the placement of $n$ objects—including the tare weight—in $n$ trials. Suppose the left pan of the balance scale adds to the measurement and the right pan subtracts from the measurement. Each element of this matrix $w_{ij}$ will have:

$w_{ij}={\begin{cases}0&{\text{if on the }}j{\text{th trial the }}i{\text{th object was not measured}}\\1&{\text{if on the }}j{\text{th trial the }}i{\text{th object was placed in the left pan}}\\-1&{\text{if on the }}j{\text{th trial the }}i{\text{th object was placed in the right pan }}\\\end{cases}}$

Let ${\mathbf {x}}$ be a column vector of the measurements of each of the $n$ trials, let ${\mathbf {e}}$ be the errors to these measurements each independent and identically distributed with variance $\sigma ^{2}$, and let ${\mathbf {y}}$ be a column vector of the true weights of each of the $n$ objects. Then we have:

${\mathbf {x}}=W{\mathbf {y}}+{\mathbf {e}}$

Assuming that $W$ is non-singular, we can use the method of least-squares to calculate an estimate of the true weights:

${\mathbf {y}}=(W^{T}W)^{-1}W{\mathbf {x}}$

The variance of the estimated ${\mathbf {y}}$ vector cannot be lower than ${\tfrac {\sigma ^{2}}{n}}$, and will be minimum if and only if $W$ is a weighing matrix.

Examples

Note that when weighing matrices are displayed, the symbol $-$ is used to represent −1. Here are two examples:

This is a $W(2,2)$:

${\begin{pmatrix}1&1\\1&-\end{pmatrix}}$

This is a $W(7,4)$:

${\begin{pmatrix}1&1&1&1&0&0&0\\1&-&0&0&1&1&0\\1&0&-&0&-&0&1\\1&0&0&-&0&-&-\\0&1&-&0&0&1&-\\0&1&0&-&1&0&1\\0&0&1&-&-&1&0\end{pmatrix}}$

Equivalence

Two weighing matrices are considered to be equivalent if one can be obtained from the other by a series of permutations and negations of the rows and columns of the matrix. The classification of weighing matrices is complete for cases where $w$ ≤ 5 as well as all cases where $n$ ≤ 15 are also completed. However, very little has been done beyond this with exception to classifying circulant weighing matrices.

Open Questions

There are many open questions about weighing matrices. The main question about weighing matrices is their existence: for which values of $n$ and $w$ does there exist a $W(n,w)$? A great deal about this is unknown. An equally important but often overlooked question about weighing matrices is their enumeration: for a given $n$ and $w$, how many $W(n,w)$'s are there?

This question has two different meanings. Enumerating up to equivalence and enumerating different matrices with same n,k parameters. Some papers were published on the first question but none were published on the second important question.