Complexity of computing interval matrix powers for special classes of matrices
Computing powers of interval matrices is a computationally hard problem. Indeed, it is NP-hard even when the exponent is 3 and the matrices only have interval components in one row and one column. Motivated by this result, we consider special types of interval matrices where the interval components occupy specific positions. We show that computing the third power of matrices with only one column occupied by interval components can be solved in cubic time; so the asymptotic time complexity is the...