The significant increases in flexural strength achieved in macro-defect-free cements have been attributed to a reduction in the density of defects in the materials as well as to chemical reactions occurring between the organic constituent, i.e., the poly(vinyl alcohol) (PVA) polymer, and inorganic ions coming from the hydration products of the cement. In particular, it has been suggested that PVA chains are partially linked together by Al ions. This phenomenon has been investigated here by studying the structure and the energetics of Al-PVA models with ab initio theoretical methods. The achieved results strongly support the existence of a cross-linking of PVA chains by Al ions, even in the presence of structural deformations of the PVA chains. The vibrational frequency of a stretching mode related to the O atoms bonded with Al has been also evaluated, which may represent a fingerprint for an experimental identification of cross-linking.