So, it was given that soldiers marching in unison go out of step while crossing a bridge to avoid any damage or collapse of the bridge.
Here is a notice on the Albert Bridge in London.
The Angers Bridge in France collapsed on 16 April 1850, while a battalion of French soldiers was marching across it, killing over 200 of them.
The Tacoma Narrows Bridge collapsed due to wind induced aeroelastic flutter.
These are examples of resonance where the frequency of a periodic force (soldiers marching in step, wind induced aeroelastic flutter, etc) applied to the bridge is equal to one of the natural frequencies of vibration of the bridge - resonance.
Further, if they don't march in unison and starts walking with different frequencies, then the chances of natural frequency of the bridge being equal to the walking frequency of one of the man would increase, and this could cause resonance and the collapse of the bridge, wouldn't it?
Interestingly enough the oscillations of a bridge can influence how people walk across the bridge which via a positive feedback effect can then increase the amplitude of the oscillations.
Civil Engineering is an evolving science.
The Millennium Bridge for pedestrians across the River Thames in London was opened on June 10, 2000 and then closed a few days later due to excessive swaying.
It had been carefully designed and although a relatively flexible suspended structure it was though that there would not be a problem when pedestrians crossed it as the pedestrians would not all be walking it step at a frequency equal to the natural frequency of the bridge.
The design was such that vertical forces due to the pedestrians walking across the bridge would not produce a significant resonance effect.
However, to the surprise of the design team, the lateral swaying of the bridge at its natural frequency made pedestrians unstable and to compensate they walked in step with the movement of the bridge with their legs apart and applying lateral forces on the bridge at the natural frequency of the bridge thus causing increasing oscillations of the bridge which in turn made more pedestrians walk in step - a resonance effect.

The solution to the problems was to add dampers to the bridge which reduced the Q-value of the resonance - the energy of oscillation was converted into heat via frictional forces and the amplitude of oscillation was significantly smaller than before.
The paper Lateral excitation of bridges by balancing pedestrians gives an insight to the Millennium Bridge effect.