El diagrama de parejas [8], es un producto
carteseano obtenido a través de las matrices de conectividad del diagrama de de Bruijn.
El diagrama de parejas es útil para comparar caminos entre dos diagramas diferentes o dos
caminos en el mismo diagrama. Las flechas dentro del diagrama de parejas se derivan del
hecho de que para algún nodo (formado por una pareja de estados) cualesquiera de la
gráfica, evolucione en parejas ordenadas en un mismo estado a otro nodo. Es decir, los
índices de la matriz topológica del diagrama de parejas estan formadas por todas las
parejas ordenadas que se llegan a formar del número de estados del diagrama de de Bruijn
y nos da un total de 
nodos
en el diagrama de parejas. Una gran útilidad que nos brinda el diagrama de parejas es
obtener los múltiples ancestros dentro de los autómatas celulares, ya que podemos
extraer secuencias que formen un ciclo dentro del diagrama y comprobar si estas secuencias
por los mismos nodos tienen más de un ancestro para una vecindad dada. Con esto cabe
señalar que en el diagrama de parejas se pueden obtener todos los ciclos que pueden
existir dentro del autómata en estudio.
Producto cartesiano. [17]
Sean A y B dos conjuntos y C el conjunto producto que
representamos como 
cuyos
elementos van a ser los distintos pares o parejas que se puedan formar tomando todos y
cada uno de los elementos de A, con todos y cada uno de los elementos de B,
de esta manera si a es un elemento de A y b un elemento de B
entonces,
Para determinar el orden de la matriz C consideremos las matrices de
conectividad por estado del diagrama de de Bruijn de orden n, 
y 
.
Por lo tanto, el diagrama como tal describe parejas ordenadas y consecuentemente la matriz
de conectividad C tiene propiedades simétricas así como reflexivas, por lo que
nos permite construir un diagrama desordenado en donde la distinción entre los elementos
de las parejas 
y 
es practicamente
insignificante.