Suppose A is a scheme with d classes. Since C[A ] is closed under multiplica-
tion, there are constants pi,j(k) such that
Ai Aj =
X
d
k=0
pi,j(k)Ak.
We call these the intersection numbers of the scheme. We see that
pi,j(k)Ak = Ak ◦ (Ai Aj),
from which it follows that the intersection numbers are non-negative integers.
We see also that
pi,j(k) =
sum(Ak ◦ (Ai Aj))
v vk
=
tr(A
T
k
Ai Aj)
v vk
. (2.3.1)
We define the intersection matrices B0,...,Bd by
(Bi)j,k := pi,j(k).
If π denotes the relation partition of V (A ) with respect to v, then Bi = A/π.

This excerpt is focused on algebraic combinatorics and specifically deals with association schemes and their intersection numbers. Let's break down the notation and concepts for clarity.

### Key Concepts:

1. **Scheme with d Classes (A):**  
   The scheme \( A \) refers to an association scheme, which is a structured set of relations or classes on a finite set. The scheme has \( d \) classes, meaning there are \( d \) distinct relations.

2. **Algebra of Matrices \( C[A] \):**  
   \( C[A] \) represents the set of adjacency matrices associated with the relations in the scheme. Since it's closed under multiplication, any product of two matrices in \( C[A] \) can be expressed as a linear combination of the matrices in the set.

3. **Intersection Numbers \( p_{i,j}(k) \):**  
   These are constants that arise when multiplying the adjacency matrices of the relations \( A_i \) and \( A_j \). Specifically, the product \( A_i A_j \) can be written as:
   \[
   A_i A_j = \sum_{k=0}^d p_{i,j}(k) A_k,
   \]
   where the \( p_{i,j}(k) \) are called intersection numbers. They indicate how the product of two relations in the scheme can be decomposed into the other relations.

4. **Non-negative Integers:**  
   The intersection numbers \( p_{i,j}(k) \) are non-negative integers. This property follows from the fact that \( p_{i,j}(k) A_k \) can be interpreted as the number of times the relation \( A_k \) occurs when composing the relations \( A_i \) and \( A_j \).

5. **Intersection Matrices \( B_0, \dots, B_d \):**  
   The matrices \( B_i \) are defined by:
   \[
   (B_i)_{j,k} := p_{i,j}(k),
   \]
   which means the entry in the \( j \)-th row and \( k \)-th column of \( B_i \) is the intersection number \( p_{i,j}(k) \).

6. **Relation Partition \( \pi \):**  
   The notation \( \pi \) represents the partition of the vertex set \( V(A) \) with respect to a particular vertex \( v \). The matrix \( B_i = A/\pi \) implies that the matrix \( A_i \) is viewed as a quotient with respect to the partition \( \pi \).

### Important Formula:

The intersection numbers \( p_{i,j}(k) \) are given by:
\[
p_{i,j}(k) = \frac{\text{sum}(A_k \circ (A_i A_j))}{v \cdot v_k} = \frac{\text{tr}(A_k^T A_i A_j)}{v \cdot v_k}.
\]
Here, the numerator involves the trace (sum of the diagonal elements) of the product of matrices, and the denominator normalizes this sum with respect to the vertices.

### Example Usage:

Consider a simple association scheme where \( d = 2 \). The intersection matrices \( B_0, B_1, B_2 \) will be 3 matrices (one for each class), and each matrix entry \( (B_i)_{j,k} \) gives the intersection number \( p_{i,j}(k) \).

This structure is often studied in the context of symmetric association schemes, strongly regular graphs, or even coding theory, where these matrices and numbers play a key role in characterizing the algebraic properties of the scheme.

### Questions:

1. What is the significance of the relation partition \( \pi \) in the context of association schemes?
2. How do the intersection matrices relate to the eigenvalues of the scheme's adjacency matrices?
3. Can you provide an example of calculating intersection numbers for a small association scheme?
4. What are the implications of the non-negativity of intersection numbers in combinatorial design?
5. How do these concepts extend to infinite association schemes, if at all?

### Tip:

Understanding the connection between algebraic structures (like matrices) and combinatorial objects (like graphs or schemes) can offer deep insights into both areas. Explore how changes in one representation (e.g., matrix operations) affect the combinatorial interpretation.

Suppose A is a scheme with d classes. Since C[A ] is closed under multiplication, there are constants pi,j(k) such that Ai Aj = Xd k=0 pi,j(k)Ak. We call these the intersection numbers of the scheme. We see that pi,j(k)Ak = Ak ◦ (Ai Aj), from which it follows that the intersection numbers are non-negative integers. We see also that pi,j(k) = sum(Ak ◦ (Ai Aj)) / (v vk) = tr(Ak^T Ai Aj) / (v vk). (2.3.1) We define the intersection matrices B0,...,Bd by (Bi)j,k := pi,j(k). If π denotes the relation partition of V(A ) with respect to v, then Bi = A/π.

Explore the concept of intersection numbers in algebraic combinatorics, focusing on how they arise from matrix algebra in association schemes. Learn the key formulas, including Ai Aj = Σd_k=0 pi,j(k) Ak, and their role in defining intersection matrices. Suitable for advanced undergraduates or graduate students.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation