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 = Total[Ramp[ M], TensorRank[M]];
sumNegative = Total[Ramp[-M], TensorRank[M]];
sumNegative[n_] := sumNegative[n] = Plus[
sumPositive[n - 1] sumNegative,
sumNegative[n - 1] sumPositive
];
sumPositive[n_] := sumPositive[n] = Plus[
sumPositive[n - 1] sumPositive,
sumNegative[n - 1] sumNegative
];

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