Problem 2 - Mathematics

For real numbers , define an $n \times n$ matrix by . Let $H$ be a set of $n$-dimensional vectors whose element sum is equal to 1. For , defined by

1.

Show . When does hold?

2.

Preprocess data to form an appropriate data structure so that, when a new is given, finding the smallest among can be found efficiently. Also, analyse the complexity of the algorithm.