A quick way to calculate the next product


1) a 1xn

vector a


2) a nx1

vector b


3) a nxn

matrix X


the problem is getting an iterative method that can compute the product


as fast as possible, where parenthesis {Y}

is a user-defined operator that returns a matrix whose diagonal elements are all zero and whose off-diagonal elements are equal to the elements of the matrix Y



Without the parenthesis operator {}

, if we need to compute the product a*X*X*X*X*X*X*b

, I think we can naturally concatenate the matrix multiplication operator *

like this:


so it's a total time complexity O(n^2)

. However, when it comes to calculating


I don't know how to change the kind of association *

. I would appreciate it if someone could give me some advice to show the possibility of iterative computation a*{X*{X*{X*X}*X}*X}*b

at the same time O(n^2)

, rather than O(n^3)



source to share

1 answer

I doubt we will come up with the o(matrix-multiplication(n))

-time algorithm today, the next drop. However, it is possible for the use of space to be linear.

Let {Y} = Y - diag(Y)

. I will consider a simpler computation problem a*{X*{X*X}*X}*b'

. Using linearity diag

, we write

{X*{X*X}*X} = {X*(X*X - diag(X*X))*X}
            = X*(X*X - diag(X*X))*X - diag(X*(X*X - diag(X*X))*X)
            = X*X*X*X - X*diag(X*X)*X - diag(X*X*X*X - X*diag(X*X)*X)
            = X*X*X*X - X*diag(X*X)*X - diag(X*X*X*X) + diag(X*diag(X*X)*X).


Now let's look at each term in turn. The first term is a*X*X*X*X*b' = ((a*X)*X)*(X*(X*b'))

calculated using operations O(n^2)

. The second term is a*X*diag(X*X)*X*b' = (a*X)*diag(X*X)*(X*b')

also. So the fourth term a*diag(X*diag(X*X)*X)*b'


The third term is problematic, a*diag(X*X*X*X)*b'

. Since the other three are computable with operations O(n^2)

, this is equivalent in some sense to the whole computation.

Let j

- all-one vector. Then j*diag(X*X*X*X)*j' = tr(X^4)

. If X

is the adjacency matrix of the graph, then tr(X^4)

is the number of (possibly degenerate) 4-cycles. Assuming an undirected simple graph, the number of degenerate 4-cycles is given by a simple function of the sequence of degrees. the prior art in counting cycles does not appear to be better than matrix multiplication.



All Articles