We work with the max algebra of the set of real numbers together with minus infinity, equipped with the binary operations of maximization and addition. For a square matrix, its permanent over the max algebra is simply the maximum diagonal sum of the matrix. Several results are proved for the permanent over the max algebra which are analogs of the corresponding results for the permanent of a nonnegative matrix. These include Alexandroff Inequality and Cauchy-Binet formula. Normally such results are proved by employing the "transfer principle" but we indicate a different proof technique which uses the duality theorem of linear programming, which is applicable in some cases.