# A quick way to calculate the next product

Considering

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

`a*{X*{X*{X*X}*X}*X}*b`

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`

.

** Note:**

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:

`(((a*X)*X)*X)*(X*(X*(X*b)))`

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

. However, when it comes to calculating

`a*{X*{X*{X*X}*X}*X}*b`

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

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.

source to share