Multiple underbraces that span overlapping columns in matrix

Here is a quick take on what might be possible if you're not really interested in generalization:

\documentclass{article}
\usepackage{amsmath}% http://ctan.org/pkg/amsmath
\newcommand{\mydots}[1]{\makebox[0pt][l]{$\underbrace{1\ 1\ \cdots\ 1}_{#1}$}}
\begin{document}
\[
  \begin{pmatrix}
    \mydots{s} & \\
    & \hspace*{3em}\mydots{s} & \\
    & & \hspace*{3em}\ddots & \\
    & & & \mydots{s} & \hspace{3em}
  \end{pmatrix}
\]
\end{document}

The idea is to set the construction (the \underbrace structure) with a right overlap (not really necessary) and space appropriately.

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}
$\displaystyle
\begin{pmatrix}
  \tikzmark[1-1]{1} & 1 & \ldots & \tikzmark[1-n]{1} \\[2ex]
    & \tikzmark[2-1]{1} & \ldots & 1 & \tikzmark[2-n]{1} \\[2ex]
    &   & \ddots & \\[2ex]
    &   &        & \tikzmark[n-1]{1} & \ldots & \tikzmark[n-n]{1}
\end{pmatrix}
$
\foreach \i in {1,2,n}
\tikz[remember picture,overlay]\draw[decorate,decoration={brace,amplitude=3pt,mirror}](\i-1.south west)--node[below]{$s$}(\i-n.south east);
\end{document}

Output

---

Or a full TikZ solution (without using pmatrix)

Code

\documentclass[border=5pt]{standalone}

\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing,matrix}

\begin{document}
\begin{tikzpicture}[every left delimiter/.style={xshift=1ex},every right delimiter/.style={xshift=-1ex}]
  \matrix(m)[matrix of math nodes,
    left delimiter=(,
    right delimiter=),
    row sep=2ex
  ]{
    |[name=1-1]|1 & 1             & \ldots & |[name=1-n]|1                          \\
                  & |[name=2-1]|1 & \ldots & 1             & |[name=2-n]|1          \\
                  &               & \ddots &                                        \\
                  &               &        & |[name=n-1]|1 & \ldots & |[name=n-n]|1 \\
  };
  \foreach \i in {1,2,n}
  \draw[decorate,decoration={brace,amplitude=3pt,mirror}](\i-1.south west)--node[below=1pt]{$s$}(\i-n.south east);
\end{tikzpicture}
\end{document}

Output

A variation on the other answer of mine to a similar problem in Underbrace in a matrix

\documentclass{standalone}
\usepackage{amsmath,mathtools}

\newcommand{\blockB}[1]{
  \underbrace{\!\!\begin{matrix}1 & \cdots & 1\end{matrix}\!\!}_{#1\mathstrut}
}

\begin{document}
$
  \begin{pmatrix}
  1 & \mathrlap{\blockB{k}} \\
  & 1 & \mathrlap{\blockB{k}} \\
  && 1 & \mathrlap{\blockB{k}} \\
  &&&& \ddots \\
  &&&&& 1 & \blockB{k}
  \end{pmatrix}
$
\end{document}

If you want the brace to span all the block, some more tricks are needed.

\documentclass[border=5]{standalone}
\usepackage{amsmath,mathtools}

\newcommand{\blockC}[1]{
  \,\,\underbrace{\!\!\begin{matrix}1 & 1 & \cdots & 1\end{matrix}\!\!}_{#1\mathstrut}\,\,
}

\begin{document}
$
  \begin{pmatrix}
  \hphantom{1}\mathrlap{\blockC{k}} \\
  & \hphantom{1}\mathrlap{\blockC{k}} \\
  && \hphantom{1}\mathrlap{\blockC{k}} &\hphantom{1} \\
  &&&& \ddots \\
  &&&&& \blockC{k}
  \end{pmatrix}
$
\end{document}

I use some \hphantom{1} to ensure correct alignment: they give some width to the cells.