Magic Square Check for NxN Matrix - with Minimum Complexity?
If you have an $N \times N$ matrix, then it has $N^2$ entries, and as you need to check all entries at least once to see if the square is a magic square, any algorithm must have a running time of $\Omega(N^2)$.

For a square to be a magic square, all rows, columns and both diagonals must sum to the same number. There are $N$ rows, $N$ columns and 2 diagonals, each of which have $N$ entries, so you can check this property in $O((2N+2)N) = O(N^2)$ time.

Combining the above: verifying the magicness of a square is in $\Theta(N^2)$.