Index Matrices

Why

The (surprising fact) is that the operation of going from an index list to its induced sublist is linear, if the elements of the list are over a field, and thus may be viewed as a vector space.

Definition

The index matrix associated with the index sequence $\alpha $ of length $r$ and order $n$ (recall, $r \leq n$) is the $r \times n$ matrix whose $i,j$th entry is 1 if the sequence’s $i$th coordinate is $j$, and $0$ otherwise.

Examples

Here are some order-5 index lists: $(1,2,3)$, $(3,2,1)$, $(4,5,1)$, $(5,4,3,2,1)$, $(3,)$.

The matrices corresponding to these examples are:

\[ \bmat{ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ }, \bmat{ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ }, \]

for the first two examples, and

\[ \bmat{ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ }, \bmat{ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ }, \bmat{ 0 & 0 & 1 & 0 & 0 \\ } \]

for the last three.

In this case, we refer to the induced sublist as an induced subvector. The value of index matrices is that they give induced subvectors via the usual and familiar operation of matrix multiplication. The subvector of an $n$-vector associated with a length-$r$ index sequence is the product of the sequence’s $r \times n$ corresponding index matrix with the $n$-dimensional vector.

For example, define $x = \bmat{6 & 4 & 5 & 3 & 9}^\top $. Then the subvector of $x$ associated with the index sequence $(3, 2, 1)$ is the vector $\bmat{3 & 9 & 6}^\top \in \R ^3$, because

\[ \bmat{3 & 9 & 6 } = \bmat{ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ }\bmat{6 \\ 4 \\ 5 \\ 3 \\ 9} \]

If $r = n$ then the index matrix is a permutation matrix.

Notation

Let $r \leq n$ be natural numbers. Let $\alpha : \upto{r} \to \upto{n}$ be an index sequence. Denote the index matrix associated with $\alpha $ by $P_\alpha $. This matrix $P_\alpha $ is an element of $\N ^{r \times n}$ and is defined by

\[ (P_a)_{ij} = \begin{cases} 1 & j = \alpha (i) \\ 0 & \text{otherwise} \end{cases} \]

Let $A$ be a nonempty set and let $x \in A^n$. then the subvector of $x$ associated with $P_\alpha $ (and so with $\alpha $) is

\[ P_\alpha x = \pmat{x_{\alpha (1)}, \dots , x_{\alpha (r)}} \]

We denote the product $P_\alpha x$ by $x_{\alpha }$. We denote the product $P_\alpha X P_\alpha ^\top $ by $X_{\alpha \alpha }$.