While most monocular structure-from-motion frameworks rely on sparse keypoints, it has long been acknowledged that lines represent an alternative, higher-order feature with high accuracy, repeatability, and abundant availability in man-made environments. Its exclusive use, however, is severely complicated by its inability to resolve the common bootstrapping scenario of two-view geometry. Even with stereo cameras, a one-dimensional disparity space as well as ill-posed triangulations of horizontal lines make the realization of purely line-based tracking pipelines difficult. The present paper successfully leverages the redundancy in camera matrices to alleviate this shortcoming. We present a novel stereo trifocal tensor solver, and extend it to the case of two camera matrix view-points. Our experiments demonstrate superior behavior with respect to both 2D-2D and 3D-3D alternatives. We furthermore outline the camera matrix’ ability to continuously and robustly bootstrap visual motion estimation pipelines via an integration into a robust, purely line-based visual odometry pipeline. The result leads to state-of-the-art tracking accuracy comparable to what is achieved by point-based stereo or even dense depth camera alternatives.