Multiple underbraces that span overlapping columns in matrix

I want to display the structure of a matrix as shown in the image below:

The following code shows the structure of the matrix, without the underbraces:

\documentclass{standalone}

\usepackage{amsmath}

\begin{document}
$\displaystyle \begin{pmatrix} 1 & 1 & \ldots & 1 \\ & 1 & \ldots & 1 & 1 \\ & & \ddots & \\ & & & 1 & \ldots & 1 \end{pmatrix}$
\end{document}


Here is the output:

How do I typeset the desired matrix with underbraces?

A solution using a variant of \tikzmark.

Code

\documentclass[border=5pt]{standalone}

\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing}

\newcommand\tikzmark[2][]{\tikz[remember picture,baseline=(#1.base)]\node[inner sep=0,outer sep=0](#1){#2};}

\begin{document}
$\begin{pmatrix} 1 & \mathbbm{1}^T_k \\ & 1 & \mathbbm{1}^T_k \\ && 1 & \mathbbm{1}^T_k \\ &&& \ddots & \ddots \\ &&&& 1 & \mathbbm{1}^T_k \end{pmatrix}$
\end{document}


If you decide to load TikZ then there is no excuse for using those \...dots family. They have been used in the absence of graphics tools. Now you have the monster onboard, I would suggest not being conservative and using that monster efficiently.