# Performing matrix tensor product and getting a sum of its negative entries

I am given a $$3 \times 3$$ matrix $$M$$, which only has real entries.

Is there an efficient way to do the following two operations with $$M$$?

1. For a given input $$n$$, compute the $$n$$-fold tensor product $$M^{\otimes n}$$, without having to brute-force by manually using KroneckerProduct repeatedly (I want to handle large values of $$n$$ which makes manual calculation unwieldy).

2. For the matrix $$M^{\otimes n}$$, compute the total sum of all the negative entries.

• What is a general way to do the tensor product --- something that is automated and not brute force? Sep 6 '21 at 19:59
• Do you really need the tensor product -- or only the sum? Sep 6 '21 at 20:01
• @HenrikSchumacher I needed both, but even the sum would be helpful. I could at least do the tensor product manually, by brute force, for a few small values of n. Sep 6 '21 at 20:06
• @bbgodfrey I think OP meant tensor product, not matrix product. Sep 7 '21 at 7:23
• @HenrikSchumacher Indeed so. Thanks. Sep 7 '21 at 12:37

If it is only about the sums of negative entries, then yes.

This is how we can do it without even building the tensor/Kronecker products:

M = RandomReal[{-1, 1}, {3, 3}];
ClearAll[sumPositive];
ClearAll[sumNegative];
sumPositive[1] = Total[Ramp[ M], TensorRank[M]];
sumNegative[1] = Total[Ramp[-M], TensorRank[M]];
sumNegative[n_] := sumNegative[n] = Plus[
sumPositive[n - 1] sumNegative[1],
sumNegative[n - 1] sumPositive[1]
];
sumPositive[n_] := sumPositive[n] = Plus[
sumPositive[n - 1] sumPositive[1],
sumNegative[n - 1] sumNegative[1]
];


Test for n = 8:

n = 8;
result1 = sumNegative[n]; // MaxMemoryUsed // AbsoluteTiming
result2 = Total[Ramp[-KroneckerProduct @@ ConstantArray[M, n]], 2]; // MaxMemoryUsed // AbsoluteTiming

result1 == result2


{0.00007, 4080}

{1.63739, 688748008}

True

Notice that sumNegative[n] needs $$O(n)$$ memory and FLOPs while the brute force approach needs $$O(9^n)$$ of both.

The key idea that the sum of all entries of a tensor product is just product of the sums:

Total[KroneckerProduct[A, A], 2] == Total[A, 2]^2


Now we only have onlt to keep track of the negative and the nonnegative parts of the tensors... Combined with recursion and memoization, we are lead to sumPositive and sumNegative.

# Remark

This can even be sped up by a clever decomposition of n into smaller parts and by exploiting that

sumNegative[m + n] == Plus[
sumPositive[m] sumNegative[n],
sumNegative[m] sumPositive[n]
]
sumPositive[m + n] == Plus[
sumPositive[m] sumPositive[n],
sumNegative[m] sumNegative[n]
]


So for a clever decomposition of your number $$n$$, you can compute the sum of all nonzero entries of $$M^{\otimes n}$$ in sublinear time. E.g., $$n = 2^k$$ can be handled in $$k = \log_2(k)$$ time and memory.

• Thanks a lot! Might you explain the code? How does it bypass computing the tensor product? Sep 6 '21 at 20:11
• One specific question, what is the reasoning behind the Ramp function in Total[Ramp[M], 2]? Sep 6 '21 at 20:17
• Ramp takes just the nonnegative part of all entries in the tensor (and zeroes the negative ones). Sep 6 '21 at 20:18
• Will the same code work if $M$ is a $k \times k$ matrix (for a known $k$), instead of a $3 \times 3$ matrix? Sep 7 '21 at 18:56
• Well, you can try for yourself... But the answer is "yes". It should work for arbitrary tensors... Sep 7 '21 at 19:19