As a new manager in an academic library (I have 17 years managerial experience in other library sectors) I am finding my deputy difficult to work with - she is nearly 20 years older than me and seems to find it hard to hide her disdain for me. I give instructions to the team and then I find she has contradicted them, she hovers over me constantly when I'm doing something as if to check I'm doing it right - I feel as if I am the deputy and she is the boss! She is very fixed in her ideas ("we've always done it this way", even though I have no plans to change something!) and for the first time ever I feel unconfident in my own abilities, and ridiculously paranoid. The rest of the team have been very welcoming and I have been praised by my manager for my communication skills with them.

It's early days but apparently she worshipped the previous manager and was devastated when she left. How can I get her onside and show her that I am a good manager - which I know I am having proved myself in my other jobs. Am I fighting a losing battle?

Also talk to your HR person. He or she might be able to counsel you on the best way to proceed and what sort of tone to take with your deputy.
good luck!