Ruze's Equation

2013-10-03T01:04:50Z

199.46.200.231: /* Application to phased array */

In [[mathematics]], a '''Bose–Mesner algebra''' is a special set of [[Matrix (mathematics)|matrices]] which arise from a combinatorial structure known as an [[association scheme]], together with the usual set of rules for combining (forming the products of) those matrices, such that they form an [[associative algebra]], or, more precisely, a [[Unital algebra|unitary commutative algebra]]. Among these rules are:
:*the result of a product is also within the set of matrices,
:*there is an identity matrix in the set, and
:*such that taking products is [[Commutativity|commutative]].

Bose–Mesner algebras have applications in [[physics]] to [[spin model]]s, and in [[statistics]] to the [[design of experiments]]. They are named for [[R. C. Bose]] and Dale Marsh Mesner.<ref>Bose & Mesner (1959)</ref>

==Definition==
Let ''X'' be a set of ''v'' elements. Consider a partition of the 2-element subsets of ''X'' into ''n'' non-empty subsets, ''R''1, ..., ''R''''n'' such that:
* given an <math>x \in X</math>, the number of <math>y \in X</math> such that <math>\{x,y\} \in R_i</math> depends only on i (and not on ''x''). This number will be denoted by vi, and
* given <math>x,y \in X</math> with <math>\{x,y\} \in R_k</math>, the number of <math>z \in X</math> such that <math>\{x,z\} \in R_i</math> and <math>\{z,y\} \in R_j</math> depends only on ''i'',''j'' and ''k'' (and not on ''x'' and ''y''). This number will be denoted by <math>p^k_{ij}</math>.
This structure is enhanced by adding all pairs of repeated elements of ''X'' and collecting them in a subset ''R''0. This enhancement permits the parameters ''i'', ''j'', and ''k'' to take on the value of zero, and lets some of ''x'',''y'' or ''z'' be equal.

A set with such an enhanced partition is called an [[Association scheme]].<ref>{{harvnb|Cameron|van Lint|1991|loc=pp.197–198}}</ref> One may view an association scheme as a partition of the edges of a [[complete graph]] (with vertex set ''X'') into n classes, often thought of as color classes. In this representation, there is a loop at each vertex and all the loops receive the same 0th color.

The association scheme can also be represented algebraically. Consider the [[Matrix (mathematics)|matrices]] ''D''''i'' defined by:
: <math>(D_i)_{x,y} = \begin{cases}
1,& \text{if } \left(x,y\right)\in R_{i},\\
0,& \text{otherwise.} \end{cases} \qquad (1)</math>

Let <math>\mathcal{A}</math> be the [[vector space]] consisting of all [[Matrix (mathematics)|matrices]] <math>\sideset{}{_{i=0}^{n}}\sum a_{i}D_{i}</math>, with <math>a_{i}</math> complex.<ref>{{harvnb|Camion|1998}}</ref><ref>{{harvnb|Delsarte|Levenshtein|1998}}</ref>

The definition of an [[association scheme]] is equivalent to saying that the <math>D_{i}</math> are ''v'' × ''v'' (0,1)-[[Matrix (mathematics)|matrices]] which satisfy

# <math>D_i</math> is symmetric,
# <math>\sum_{i=0}^n D_{i}=J </math> (the all-ones matrix),
# <math>D_0=I,</math>
# <math>D_i D_j = \sum_{k=0}^n p^k_{ij} D_k = D_j D_i,\qquad i,j=0,\ldots,n.</math>

The (''x'',''y'')-th entry of the left side of 4. is the number of two colored paths of length two joining ''x'' and ''y'' (using "colors" ''i'' and ''j'') in the graph. Note that the rows and columns of <math>D_i</math> contain <math>v_i</math> 1s:

: <math>D_i J=J D_i = v_i J. \qquad (2)</math>

From 1., these [[Matrix (mathematics)|matrices]] are [[Symmetric matrix|symmetric]]. From 2., <math>D_{0},\ldots,D_{n}</math> are [[Linear independence|linearly independent]], and the dimension of <math>\mathcal{A}</math> is <math>n+1</math>. From 4., <math>\mathcal{A}</math> is closed under multiplication, and multiplication is always associative. This [[Associative algebra|associative]] [[commutative algebra]] <math>\mathcal{A}</math> is called the '''Bose–Mesner algebra''' of the [[association scheme]]. Since the [[Matrix (mathematics)|matrices]] in <math>\mathcal{A}</math> are symmetric and commute with each other, they can be simultaneously diagonalized. This means that there is a [[Matrix (mathematics)|matrix]] <math>S</math> such that to each <math>A\in\mathcal{A}</math> there is a [[diagonal matrix]] <math>\Lambda_{A}</math> with <math>S^{-1}A S=\Lambda_{A}</math>. This means that <math>\mathcal{A}</math> is semi-simple and has a unique basis of primitive idempotents <math>J_{0},\ldots,J_{n}</math>. These are complex n × n [[Matrix (mathematics)|matrices]] satisfying

: <math>
J_i^2 =J_i, i=0,\ldots,n, \qquad (3)
</math>

: <math>
J_i J_k=0, i\neq k, \qquad (4)
</math>

: <math>
\sum_{i=0}^n J_i = I. \qquad (5)
</math>

The '''Bose–Mesner algebra''' has two distinguished bases: the basis consisting of the [[Adjacency matrix|adjacency matrices]] <math>D_i</math>, and the basis consisting of the irreducible [[Idempotent matrix|idempotent matrices]] <math>E_k</math>. By definition, there exist well-defined [[complex number]]s such that

: <math>
D_{i}=\sum_{k=0}^n p_i (k) E_k, \qquad (6)
</math>

and

: <math>
|X|E_{k}=\sum_{i=0}^n q_k\left(i\right)D_i. \qquad (7)
</math>

The p-numbers <math>p_i (k)</math>, and the q-numbers <math>q_k(i)</math>, play a prominent role in the theory.<ref>{{harvnb|Camion|1998}}</ref> They satisfy well-defined orthogonality relations. The p-numbers are the [[eigenvalues]] of the [[adjacency matrix]] <math>D_i</math>.

==Theorem==

The [[eigenvalues]] of <math>p_{i}\left(k\right)</math> and <math>q_{k}\left(i\right)</math>, satisfy the orthogonality conditions:

: <math>
\sum_{k=0}^n \mu_i p_i (k)p_\ell (k)=v v_i \delta_{i \ell}, \quad(8)
</math>

: <math>
\sum_{k=0}^n \mu_i q_k (i) q_\ell (i)=v \mu_k \delta_{k \ell}. \quad(9)
</math>

Also

: <math>
\mu_j p_i (j) = v_i q_ j (i),\quad i,j=0,\ldots,n. \quad(10)
</math>

In [[Matrix (mathematics)|matrix]] notation, these are

: <math>
P^T \Delta_\mu P=v\Delta_v, \quad(11)
</math>

: <math>
Q^T \Delta_v Q=v\Delta_\mu, \quad(12)
</math>

where <math>\Delta_v = \operatorname{diag} \{v_0,v_1,\ldots,v_n\},\qquad \Delta_\mu = \operatorname{diag} \{\mu_0,\mu_1,\ldots,\mu_n\}.</math>

==Proof of theorem==

The [[eigenvalue]]s of <math>D_i D_\ell</math> are <math>p_i (k)p_\ell (k)</math> with multiplicities <math>\mu_k</math>. This implies that

: <math>
v v_i \delta_{i\ell} = \operatorname{trace}D_i D_\ell = \sum_{k=0}^n \mu_i p_i(k) p_\ell (k), \quad(13)
</math>

which proves Equation <math>\left(8\right)</math> and Equation <math>\left(11\right)</math>,

: <math>
Q = v P^{-1} = \Delta_v^{-1} P^T \Delta_\mu, \quad(14)
</math>

which gives Equations <math>(9)</math>, <math>(10)</math> and <math>(12)</math>.<math>\Box</math>

There is an analogy between extensions of [[association scheme]]s and [[Kronecker's theorem|extensions]] of [[finite field]]s. The cases we are most interested in are those where the extended schemes are defined on the <math>n</math>-th [[Cartesian power]] <math>X=\mathcal{F}^{n}</math> of a set <math>\mathcal{F}</math> on which a basic [[association scheme]] <math>\left(\mathcal{F},K\right)</math> is defined. A first [[association scheme]] defined on <math>X=\mathcal{F}^{n}</math> is called the <math>n</math>-th [[Kronecker product|Kronecker power]] <math>\left(\mathcal{F},K\right)_{\otimes}^{n}</math> of <math>\left(\mathcal{F},K\right)</math>. Next the extension is defined on the same set <math>X=\mathcal{F}^{n}</math> by gathering classes of <math>\left(\mathcal{F},K\right)_{\otimes}^{n}</math>. The [[Kronecker product|Kronecker power]] corresponds to the [[polynomial ring]] <math>F\left[X\right]</math> first defined on a [[Finite field|field]] <math>\mathbb{F}</math>, while the extension scheme corresponds to the [[extension field]] obtained as a quotient. An example of such an extended scheme is the [[Hamming scheme]].

[[Association scheme]]s may be merged, but merging them leads to non-symmetric [[association scheme]]s, whereas all usual [[code]]s are [[subgroup]]s in symmetric [[Abelian variety|Abelian schemes]].<ref>{{harvnb|Delsarte|Levenshtein|1998}}</ref><ref>{{harvnb|Camion|1998}}</ref><ref>{{harvnb|MacWilliams|Sloane|1978}}</ref>

==See also==
* [[Association scheme]]

{{More footnotes|date=September 2010}}

==Notes==

{{Reflist}}

==References==

* {{Cite book|first=Rosemary A.|last=Bailey|authorlink=Rosemary A. Bailey|url=http://www.maths.qmul.ac.uk/~rab/Asbook |title=Association schemes: Designed experiments, algebra and combinatorics|series=Cambridge Studies in Advanced Mathematics|volume=84|publisher=Cambridge University Press|year=2004|pages=387|isbn=978-0-521-82446-0| mr=2047311|ref=harv}}

* {{cite book | last1=Bannai | first1=Eiichi | last2=Ito | first2=Tatsuro | title=Algebraic combinatorics I: Association schemes | publisher=The Benjamin/Cummings Publishing Co., Inc. | location=Menlo Park, CA | year=1984 | pages=xxiv+425 | isbn=0-8053-0490-8 | mr=0882540 | unused_data= }}

* Bannai, Etsuko (2001) "Bose–Mesner algebras associated with four-weight spin models", ''Graphs and Combinatorics'', 17 (4),589–598. {{doi|10.1007/PL00007251}}

* {{citation| last1=Bose|first1=R. C.| authorlink1=R. C. Bose| last2=Mesner|first2=D. M.|year=1959|title=On linear associative algebras corresponding to association schemes of partially balanced designs|journal=[[Annals of Mathematical Statistics]]|volume=30|issue=1|pages=21–38| url=http://projecteuclid.org/euclid.aoms/1177706356 | doi=10.1214/aoms/1177706356 | mr = 102157 | jstor = 2237117}}

* {{citation|last=Cameron|first=P. J.|last2=van Lint|first2=J. H.|title=Designs, Graphs, Codes and their Links|year=1991|publisher=Cambridge University Press|location=Cambridge|isbn=0-521-42385-6}}

* {{citation|last1= Camion|first1=P.|authorlink1=Paul Camion|chapter=Codes and association schemes: Basic properties of association schemes relevant to coding| title=Handbook of coding theory|editor1-last= Pless|editor1-first=V. S.|editor1-link=Vera Pless|editor2-last=Huffman|editor2-first=W. C.|publisher=Elsevier|place= The Netherlands|year= 1998}}

* {{citation|last1=Delsarte|first1=P.|last2=Levenshtein|first2=V. I.|authorlink2=Vladimir Levenshtein|title=Association schemes and coding theory|journal=IEEE Transactions in Information Theory| volume= 44| issue= 6|pages= 2477–2504|year= 1998}}

* {{citation| first1=F. J.|last1= MacWilliams|first2=N. J. A.|last2= Sloane|authorlink2=Neil J. A. Sloane|title=The theory of error-correcting codes|publisher= Elsevier|place= New York|year= 1978}}

* Nomura, K. (1997) "An algebra associated with a spin model", ''Journal of Algebraic Combinatorics'', 6 (1), 53–58. {{DOI|10.1023/A:1008644201287}}

{{Experimental design|state=expanded}}

{{DEFAULTSORT:Bose-Mesner Algebra}}
[[Category:Algebraic combinatorics]]
[[Category:Design of experiments]]
[[Category:Analysis of variance]]
[[Category:Representation theory]]
[[Category:Algebra]]

formulasearchengine - User contributions [en]

Ruze's Equation