  We study matter effects which arise in the muon neutrino oscillation and
survival probabilities relevant to atmospheric neutrino and very long baseline
beam experiments. The inter-relations between the three probabilities P_{\mu
e}, P_{\mu \tau} and P_{\mu \mu} are examined. It is shown that large and
observable sensitivity to the neutrino mass hierarchy can be present in P_{\mu
\mu} and P_{\mu \tau}. We emphasize that at baselines of > 7000 Km, matter
effects in P_{\mu \tau} can be large under certain conditions. The muon
survival rates in experiments with very long baselines thus depend on matter
effects in both P_{\mu \tau} and P_{\mu e}. We indicate where these effects are
sensitive to \theta_{13}, and identify ranges of E and L where the event rates
increase with decreasing \theta_{13}, providing a handle to probe small
\theta_{13}. The effect of parameter degeneracies in the three probabilities at
these baselines and energies is studied in detail. Realistic event rate
calculations are performed for a charge discriminating 100 kT iron calorimeter
which demonstrate the possibility of realising the goal of determining the
neutrino mass hierarchy using atmospheric neutrinos. It is shown that a careful
selection of energy and baseline ranges is necessary in order to obtain a
statistically significant signal, and that the effects are largest in bins
where matter effects in both P_{\mu e} and P_{\mu \tau} combine constructively.
Under these conditions, upto a 4\sigma signal for matter effects is possible
(for \Delta_{31}>0) within a timescale appreciably shorter than the one
anticipated for neutrino factories.
