Einstein Notation

linear-algebra

Definition

Einstein Notation

Einstein notation (summation convention) is a notation for tensor operations in which an index that appears twice in a term is implicitly summed over its full range. Indices that appear exactly once are free and determine the output shape.

$$A_{ij}{B}_{jk}\equiv \sum _{j=1}^n{A}_{ij}{B}_{jk}$$

Indices

Free Indices

Definition

Free Index (Einstein Notation)

A free index is an index that appears exactly once in an Einstein notation term. It is not summed over and becomes an axis of the output.

Link to original

Dummy Indices

Definition

Dummy Index (Einstein Notation)

A dummy index (contracted index) is an index that appears exactly twice in an Einstein notation term. It is implicitly summed over its full range and does not appear in the output.

Link to original

Ill-formed Indices

Definition

Ill-formed Index (Einstein Notation)

In Einstein notation, an index that appears three or more times in a single term is ill-formed. The expression is undefined because the summation is ambiguous — there is no rule for which pairs to contract.

Every index in a well-formed term must be either free (once) or dummy (twice).

Link to original

The Shape Rule

The output of an expression is indexed by its free indices, in the order they appear. Each free index runs over its natural range.

Examples

Let $i\in \{1,2,\dots ,m\}$ and $j\in \{1,2,\dots n\}$ and $k\in \{1,2,\dots ,o\}$.

expression	free indices	dummy indices	output shape
$x_i$	$i$	none	vector of length $n$
$A_{ij}$	$i,j$	none	$m\times n$ matrix
$x_i{y}_i$	none	none	scalar
$x_i{y}_j$	$i,j$	none	$n\times m$ matrix
$A_{ij}{x}_j$	$i$	$j$	vector of length $m$
$x_i{A}_{ij}$	$j$	$i$	vector of length $n$
$A_{ij}{B}_{jk}$	$i,k$	$j$	$m\times o$ matrix
$A_{ij}{B}_{ji}$	none	$i,j$	scalar

Contraction

A dummy index is contracted: it matched across two factors and summed over.

$A_{ij}{x}_j$

The sum over the index dimension $j\in \{1,2,\dots ,n\}$ as its matched across two factors (dummy index), i,e.:

$$(Ax{)}_i=\sum _{j=1}^n{A}_{ij}{x}_j=\left(\begin{array}{c}{\sum }_{j=1}^n{A}_{1j}{x}_j\\ {\sum }_{j=1}^n{A}_{2j}{x}_j\\ ⋮\\ {\sum }_{j=1}^n{A}_{mj}{x}_j\end{array}\right)$$

The contraction removes the axis of dummy index $j$, thus, the output shape has fewer axes than matrix $A$.

Precondition

Every dummy index must have the same range wherever it appears.

Example

If $A_{ij}$ has $j_A\in \{1,2,\dots ,n\}$ and $B_{jk}$ has $j_B\in \{1,2,\dots ,n\}$, i.e. $j=j_A=j_B$, then the contraction over $j$ is well-defined.

If the ranges differ, the expression is ill-typed.