Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи x₁, x₂, … ,x_k-1, x_k определяется как выражение вида x₂*x₃* … x_k-1, не содержащее две концевые вершины x₁ и x_k. «Модифицированная матрица смежности» B=[β(i,j)] — это (nЧn)- матрица, в которой β(i,j) — x_j, если существует дуга из x_i в x_j и нуль в противном случае. Предположим теперь, что у нас есть матрица P_L = [p_L(i ,j)], где p_L(i,j) — сумма внутренних произведений всех простых цепей длины L (L≥1) между вершинами x_i и x_j для x_i≠x_j. Положим p_L(i,i)=0 для всех i. Обычное алгебраическое произведение матриц B*P_L = P’_L+1 = [p’_L+1(s,t)] определяется как
т.е. p’_L+1(s,t) является суммой внутренних произведений всех цепей из x_s в x_t длины l+1. Так как все цепи из x_k в x_t, представленные внутренними произведениями из p_L(k,t), являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в p_L(k,t) содержат вершину x_s. Таким образом, если из p’_L+1(s,t) исключить все слагаемые, содержащие x_s (а это можно сделать простой проверкой), то получим p_L+1(s,t). Матрица P_L+1=[p_L+1(s,t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L+1.

В
ычисляя затем B*P_L+1, находим P_L+2 и т.д., пока не будет построена матрица P_n-1, дающая все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в P_n-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B*P_n-1 (все диагональные элементы этой матрицы одинаковые).

Очевидно, что в качестве начального значения матрицы P (т.е. P₁) следует взять матрицу смежности A графа, положив все ее диагональные элементы равными нулю.

Недостатки этого метода совершенно очевидны. В процессе умножения матриц (т.е. когда L увеличивается) каждый элемент матрицы P_L будет состоять из все большего числа членов вплоть до некоторого критического значения L, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений L и для графов, обычно встречающихся на практике, число цепей длины L+1, как правило, больше, чем число цепей длины L, а для больших значений L имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда L увеличивается на единицу, то объем памяти, необходимый для хранения матрицы P_L, растет очень быстро вплоть до максимума при некотором критическом значении L, после которого этот объем снова начинает уменьшаться.

Небольшая модификация вышеприведенного метода позволяет во много раз уменьшить необходимый объем памяти и время вычислений. Так как нас интересуют только гамильтоновы циклы и, как было отмечено выше, они могут быть получены из членов внутреннего произведения любой диагональной ячейки матрицы B*P_n-1, то необходимо знать только элемент p_n-1(1,1). При этом на каждом этапе не обязательно вычислять и хранить всю матрицу P_L, достаточно лишь найти первый столбец P_L. Эта модификация уменьшает необходимый объем памяти и время вычислений в n раз. Однако даже при использовании этой модификации программа для ЭВМ, написанная на языке PL/1, который позволяет построчную обработку литер и переменное распределение памяти, не была способна найти все гамильтоновы циклы в неориентированных графах с более чем примерно 20 вершинами и средним значением степени вершины, большим 4. Использовался компьютер IBM 360/65 с памятью 120 000 байтов. Более того, даже для графа с вышеуказанными «размерами» данный метод использовал фактически весь объем памяти и время вычислений равнялось 1.8 минуты. Не такое уж незначительное время для столь небольшого графа.