Learn Portuguese (Portugal): O imperador deixou-a sair.

This relates perfectly to causative valency alternation! When you use verbs like deixar (to let) or fazer (to make), the person performing the action (the causee) takes the accusative direct object form (-a or -o) if the infinitive verb is intransitive. Because sair does not take an object, we use -a. If the second verb were transitive and took its own direct object, the causee would switch to the dative -lhe.

Would it be grammatically correct to attach the pronoun to the infinitive, saying deixou saí-la?

No. In Portuguese causative constructions, the conjugated verb (deixou) and the infinitive (sair) form a tight syntactic unit. Because they function as a single block, the pronoun must attach to the conjugated verb, giving us deixou-a sair.

Since deixou ends in a vowel, why isn't the pronoun spelled as -na?

Object pronouns only transform into -na or -no when the preceding verb ends in a nasal sound (such as -m, -ão, or -õe). The -ou in deixou is an oral diphthong, meaning the sound is not nasalized. Therefore, the pronoun keeps its standard form -a.

Where would the pronoun go if the sentence were negative?