The Hessian of a neural network captures parameter interactions through second-order derivatives of the loss. It is a fundamental object of study, closely tied to various problems in deep learning, including model design, optimization, and generalization. Most prior work has been empirical, typically focusing on low-rank approximations and heuristics that are mostly blind to the network structure.  In contrast, we develop theoretical tools to analyze the range of the Hessian map, which provides us with a precise understanding of its rank deficiency and the structural reasons behind it. This yields exact formulas and tight upper bounds for the Hessian rank of deep linear networks --- allowing for an elegant interpretation in terms of rank deficiency.  Further, by relying on a Toeplitz representation, we extend our results to the case of deep linear convolutional networks. Moreover, we demonstrate that our bounds remain faithful as an estimate of the numerical Hessian rank, for a larger class of networks with non-linearities such as rectified and hyperbolic tangent networks. Overall, our work generalizes and further establishes the key insight that the Hessian rank grows as the square root of the number of parameters --- thus providing novel insights into the source and extent of redundancy in overparameterized neural networks.