Practical Applications of a SDMS (Scientific Data Management System)

Weighing matrices are so called because of their use in optimally measuring the individual weights of multiple objects.^[1]^[2]

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)$ .^[3]

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, including some objects in the opposite pan of the scale where they subtract from the measurement.^[1]^[2]

Properties

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

The rows of $W$ are pairwise 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.^[3] As two special cases, a $W(n,n)$ is a Hadamard matrix^[3] and a $W(n,n-1)$ is equivalent to a conference matrix.

Applications

Experiment design

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}$ .^[4] 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 }}i{\text{th trial the }}j{\text{th object was not measured}}\\1&{\text{if on the }}i{\text{th trial the }}j{\text{th object was placed in the left pan}}\\-1&{\text{if on the }}i{\text{th trial the }}j{\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 $\sigma ^{2}/n$ , and will be minimum if and only if $W$ is a weighing matrix.^[4]^[5]

Optical measurement

Weighing matrices appear in the engineering of spectrometers, image scanners,^[6] and optical multiplexing systems.^[5] The design of these instruments involve an optical mask and two detectors that measure the intensity of light. The mask can either transmit light to the first detector, absorb it, or reflect it toward the second detector. The measurement of the second detector is subtracted from the first, and so these three cases correspond to weighing matrix elements of 1, 0, and −1 respectively. As this is essentially the same measurement problem as in the previous section, the usefulness of weighing matrices also applies.^[6]

Orthogonal designs

An orthogonal design of order $n$ and type $(s_{1},\dots ,s_{u})$ where $s_{i}$ are positive integers, is an $n\times n$ matrix whose entries are in the set $\{0,\pm x_{1},\dots ,\pm x_{u}\}$ , where $x_{i}$ are commuting variables. Additionally, an orthogonal design must satisfy:

XX^{T}=\sum _{i=0}^{u}s_{i}x_{i}^{2}

This constraint is also equivalent to the rows of $X$ being orthogonal and each row having exactly $s_{i}$ occurrences of $x_{i}$ .^[7] An orthogonal design can be denoted as $\mathrm {OD} (n;s_{1},\dots ,s_{u})$ .^[8] An orthogonal design of one variable is a weighing matrix, and so the two fields of study are connected.^[7] Because of this connection, new orthogonal designs can be discovered by way of weighing matrices.^[9]

Examples

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

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

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

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

{\begin{pmatrix}1&1&1&0\\1&-&0&1\\1&0&-&-\\0&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}}

Another $W(7,4)$ :

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

Which is circulant, i.e. each row is a cyclic shift of the previous row. Such a matrix is called a $CW(n,k)$ and is determined by its first row. Circulant weighing matrices are of special interest since their algebraic structure makes them easier for classification. Indeed, we know that a circulant weighing matrix of order $n$ and weight $k$ must be of square weight. So, weights $1,4,9,16,...$ are permissible and weights $k\leq 25$ have been completely classified.^[10] Two special (and actually, extreme) cases of circulant weighing matrices are (A) circulant Hadamard matrices which are conjectured not to exist unless their order is less than 5. This conjecture, the circulant Hadamard conjecture first raised by Ryser, is known to be true for many orders but is still open. (B) $CW(n,k)$ of weight $k=s^{2}$ and minimal order $n$ exist if $s$ is a prime power and such a circulant weighing matrix can be obtained by signing the complement of a finite projective plane. Since all $CW(n,k)$ for $k\leq 25$ have been classified, the first open case is $CW(105,36)$ . The first open case for a general weighing matrix (certainly not a circulant) is $W(35,25)$ .

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\leq 5$ as well as all cases where $n\leq 15$ are also completed.^[11] However, very little has been done beyond this with exception to classifying circulant weighing matrices.^[12]^[13]

Existence

One major open question about weighing matrices is their existence: for which values of $n$ and $w$ does there exist a $W(n,w)$ ? The following conjectures have been proposed about the existence of $W(n,w)$ :^[7]

If $n\equiv 2{\pmod {4}}$ then there exists a $W(n,w)$ if and only if $w<n-1$ is the sum of two integer squares.
If $n\equiv 0{\pmod {4}}$ then there exists a $W(n,w)$ for each $w<n$ .
If $n\equiv 4{\pmod {8}}$ then there exists an orthogonal design $\mathrm {OD} (n;1,1)$ for all $k<n$ where $k$ is the sum of three integer squares.
If $n\equiv 0{\pmod {8}}$ then there exists an orthogonal design $\mathrm {OD} (n;1,k)$ for all $k<n$ .
If $n\equiv 2{\pmod {4}}$ then there exists an orthogonal design $\mathrm {OD} (n;1,k)$ for all $k<n-1$ such that $k=a^{2}$ , $a$ an integer.

Although the last three conjectures are statements on orthogonal designs, it has been shown that the existence of an orthogonal design $\mathrm {OD} (n;s_{1},\dots ,s_{u})$ is equivalent to the existence of $X_{1},\dots ,X_{u}$ weighing matrices of order $n$ where $X_{i}$ has weight $s_{i}$ .^[7]

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?

References

^ ^a ^b Raghavarao, Damaraju (1960). "Some Aspects of Weighing Designs". The Annals of Mathematical Statistics. 31 (4). Institute of Mathematical Statistics: 878–884. doi:10.1214/aoms/1177705664. ISSN 0003-4851.
^ ^a ^b Seberry, Jennifer (2017). "Some Algebraic and Combinatorial Non-existence Results". Orthogonal Designs. Cham: Springer International Publishing. pp. 7–17. doi:10.1007/978-3-319-59032-5_2. ISBN 978-3-319-59031-8.
^ ^a ^b ^c Geramita, Anthony V.; Pullman, Norman J.; Wallis, Jennifer S. (1974). "Families of weighing matrices". Bulletin of the Australian Mathematical Society. 10 (1). Cambridge University Press (CUP): 119–122. doi:10.1017/s0004972700040703. ISSN 0004-9727. S2CID 122560830.
^ ^a ^b Raghavarao, Damaraju (1971). "Weighing Designs". Constructions and combinatorial problems in design of experiments. New York: Wiley. pp. 305–308. ISBN 978-0471704850.
^ ^a ^b Koukouvinos, Christos; Seberry, Jennifer (1997). "Weighing matrices and their applications". Journal of Statistical Planning and Inference. 62 (1). Elsevier BV: 91–101. doi:10.1016/s0378-3758(96)00172-3. ISSN 0378-3758. S2CID 122205953.
^ ^a ^b ^c Sloane, Neil J. A.; Harwit, Martin (1976-01-01). "Masks for Hadamard transform optics, and weighing designs". Applied Optics. 15 (1). The Optical Society: 107–114. Bibcode:1976ApOpt..15..107S. doi:10.1364/ao.15.000107. ISSN 0003-6935. PMID 20155192.
^ ^a ^b ^c ^d Geramita, Anthony V.; Seberry, Jennifer (1974). "Orthogonal designs III: weighing matrices". Utilitas Mathematica.
^ Charles J. Colbourn (1996). "Orthogonal Designs". In Colbourn, Charles J. (ed.). CRC Handbook of Combinatorial Designs (1 ed.). Boca Raton: CRC Press. p. 400. doi:10.1201/9781003040897. ISBN 9781003040897.
^ Kotsireas, Ilias; Koukouvinos, Christos; Seberry, Jennifer (2008). "New orthogonal designs from weighing matrices". Australasian Journal of Combinatorics. 40: 99–104.
^ Arasu, K.T.; Gordon, Daniel M.; Zhang, Yiran (2019). "New Nonexistence Results on Circulant Weighing Matrices". arXiv:1908.08447v3. {{cite journal}}: Cite journal requires |journal= (help)
^ Harada, Masaaki; Munemasa, Akihiro (2012). "On the classification of weighing matrices and self-orthogonal codes". J. Combin. Designs. 20: 40–57. arXiv:1011.5382. doi:10.1002/jcd.20295. S2CID 1004492.
^ Ang, Miin Huey; Arasu, K.T.; Lun Ma, Siu; Strassler, Yoseph (2008). "Study of proper circulant weighing matrices with weight 9". Discrete Mathematics. 308 (13): 2802–2809. doi:10.1016/j.disc.2004.12.029.
^ Arasu, K.T.; Hin Leung, Ka; Lun Ma, Siu; Nabavi, Ali; Ray-Chaudhuri, D.K. (2006). "Determination of all possible orders of weight 16 circulant weighing matrices". Finite Fields and Their Applications. 12 (4): 498–538. doi:10.1016/j.ffa.2005.06.009.

[Raghavarao1960-1] Raghavarao, Damaraju (1960). "Some Aspects of Weighing Designs". The Annals of Mathematical Statistics. 31 (4). Institute of Mathematical Statistics: 878–884. doi:10.1214/aoms/1177705664. ISSN 0003-4851.

[Seberry2017-2] Seberry, Jennifer (2017). "Some Algebraic and Combinatorial Non-existence Results". Orthogonal Designs. Cham: Springer International Publishing. pp. 7–17. doi:10.1007/978-3-319-59032-5_2. ISBN 978-3-319-59031-8.

[Geramita1974-3] Geramita, Anthony V.; Pullman, Norman J.; Wallis, Jennifer S. (1974). "Families of weighing matrices". Bulletin of the Australian Mathematical Society. 10 (1). Cambridge University Press (CUP): 119–122. doi:10.1017/s0004972700040703. ISSN 0004-9727. S2CID 122560830.

[Raghavarao1971-4] Raghavarao, Damaraju (1971). "Weighing Designs". Constructions and combinatorial problems in design of experiments. New York: Wiley. pp. 305–308. ISBN 978-0471704850.

[Koukouvinos1997-5] Koukouvinos, Christos; Seberry, Jennifer (1997). "Weighing matrices and their applications". Journal of Statistical Planning and Inference. 62 (1). Elsevier BV: 91–101. doi:10.1016/s0378-3758(96)00172-3. ISSN 0378-3758. S2CID 122205953.

[Sloane1976-6] Sloane, Neil J. A.; Harwit, Martin (1976-01-01). "Masks for Hadamard transform optics, and weighing designs". Applied Optics. 15 (1). The Optical Society: 107–114. Bibcode:1976ApOpt..15..107S. doi:10.1364/ao.15.000107. ISSN 0003-6935. PMID 20155192.

[Geramita1974_2-7] Geramita, Anthony V.; Seberry, Jennifer (1974). "Orthogonal designs III: weighing matrices". Utilitas Mathematica.

[Colbourn1996-8] Charles J. Colbourn (1996). "Orthogonal Designs". In Colbourn, Charles J. (ed.). CRC Handbook of Combinatorial Designs (1 ed.). Boca Raton: CRC Press. p. 400. doi:10.1201/9781003040897. ISBN 9781003040897.

[kotsireas2008new-9] Kotsireas, Ilias; Koukouvinos, Christos; Seberry, Jennifer (2008). "New orthogonal designs from weighing matrices". Australasian Journal of Combinatorics. 40: 99–104.

[Arasu2021-10] Arasu, K.T.; Gordon, Daniel M.; Zhang, Yiran (2019). "New Nonexistence Results on Circulant Weighing Matrices". arXiv:1908.08447v3. {{cite journal}}: Cite journal requires |journal= (help)

[Harada2012-11] Harada, Masaaki; Munemasa, Akihiro (2012). "On the classification of weighing matrices and self-orthogonal codes". J. Combin. Designs. 20: 40–57. arXiv:1011.5382. doi:10.1002/jcd.20295. S2CID 1004492.

[Ang2008-12] Ang, Miin Huey; Arasu, K.T.; Lun Ma, Siu; Strassler, Yoseph (2008). "Study of proper circulant weighing matrices with weight 9". Discrete Mathematics. 308 (13): 2802–2809. doi:10.1016/j.disc.2004.12.029.

[Arasu2006-13] Arasu, K.T.; Hin Leung, Ka; Lun Ma, Siu; Nabavi, Ali; Ray-Chaudhuri, D.K. (2006). "Determination of all possible orders of weight 16 circulant weighing matrices". Finite Fields and Their Applications. 12 (4): 498–538. doi:10.1016/j.ffa.2005.06.009.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Matrix classes
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz-stable Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Routh-Hurwitz Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematics portal List of matrices Category:Matrices