This paper investigates the relationship between entanglement and non-stabilizerness (magic) in matrix product states (MPSs). The study focuses on two scenarios: full-state magic and mutual magic, which are used to analyze the behavior of magic and entanglement in spin-1 anisotropic Heisenberg chains. The results show that non-stabilizerness converges more quickly with bond dimension compared to entanglement. At critical points and large volumes, full-state magic converges with $1/\chi^2$, where $\chi$ is the bond dimension. For small volumes, magic saturation is so rapid that finite-$\chi$ corrections are not detectable within error bars. Mutual magic also converges quickly with bond dimension, though sampling errors hinder the determination of its functional form. The study also demonstrates that Pauli-Markov chains can efficiently compute mutual information for MPS, which is crucial for understanding the scaling of mutual information between connected partitions at critical points. Mutual information scales logarithmically with system size, while mutual magic scales more slowly with partition size. For disconnected partitions, both mutual information and mutual magic remain constant with size. The paper highlights the importance of non-stabilizerness in quantum computing and its connection to entanglement in many-body systems. It shows that non-stabilizerness can be efficiently computed using MPS and that the bond dimension is directly related to entanglement. The results suggest a strong connection between magic and entanglement in MPS, with magic converging faster than entanglement. The study also demonstrates that Pauli-Markov chains provide a more efficient method for computing mutual information compared to traditional exact tensor network contraction methods. Overall, the findings contribute to the understanding of the role of non-stabilizerness in quantum many-body systems and its relationship with entanglement.This paper investigates the relationship between entanglement and non-stabilizerness (magic) in matrix product states (MPSs). The study focuses on two scenarios: full-state magic and mutual magic, which are used to analyze the behavior of magic and entanglement in spin-1 anisotropic Heisenberg chains. The results show that non-stabilizerness converges more quickly with bond dimension compared to entanglement. At critical points and large volumes, full-state magic converges with $1/\chi^2$, where $\chi$ is the bond dimension. For small volumes, magic saturation is so rapid that finite-$\chi$ corrections are not detectable within error bars. Mutual magic also converges quickly with bond dimension, though sampling errors hinder the determination of its functional form. The study also demonstrates that Pauli-Markov chains can efficiently compute mutual information for MPS, which is crucial for understanding the scaling of mutual information between connected partitions at critical points. Mutual information scales logarithmically with system size, while mutual magic scales more slowly with partition size. For disconnected partitions, both mutual information and mutual magic remain constant with size. The paper highlights the importance of non-stabilizerness in quantum computing and its connection to entanglement in many-body systems. It shows that non-stabilizerness can be efficiently computed using MPS and that the bond dimension is directly related to entanglement. The results suggest a strong connection between magic and entanglement in MPS, with magic converging faster than entanglement. The study also demonstrates that Pauli-Markov chains provide a more efficient method for computing mutual information compared to traditional exact tensor network contraction methods. Overall, the findings contribute to the understanding of the role of non-stabilizerness in quantum many-body systems and its relationship with entanglement.