$\newcommand{\matr}[1]{\textit{#1}} $
Consider an $n \times m$ matrix $\matr{A}$, an $m \times n$ matrix $\matr{X}$, an $m \times 1$ vector $\textbf{x}$, and an $n \times 1$ vector $\textbf{b}$, where $n \leq m$ and all entries of $\matr{A}$ and $\textbf{b}$ are real and nonnegative.
Furthermore, $\textbf{x}$ is the first column of $\matr{X}$, and diag$\left(\matr{A}\matr{X} \right) = \textbf{b}$.
Given $\matr{A}$, $\textbf{b}$, and the fact that the entries of $\matr{X}$
$\begin{equation} x_{i,j} = \begin{cases} 0, & \text{if}\ i<j \\ x_{i-j}, & \text{otherwise} \end{cases} \end{equation}, $
and the entries of $\matr{X}$
$\begin{equation} a_{i,j} = \begin{cases} 0, & \text{if}\ i>j \\ a_{i,j}, & \text{otherwise} \end{cases} \end{equation}. $
(1) Under what conditions is there a solution (or range of solutions) for $\textbf{x}$?
(2) How can we solve for $\textbf{x}$ (or range of solutions) given that the conditions are met?
I am not sure how to go about an analytic solution. So far I approximate solutions using Monte-Carlo methods. It seems like it's an underdetermined system, but for many values of $\textbf{b}$ there doesn't seem to be a solution for $\textbf{x}$. Any help/hints are greatly appreciated!
In case my notation is unclear, here is a simple example for $n=3$, $m=4$.
$ A= \begin{bmatrix} a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3}\\ 0 & a_{1,1} & a_{1,2} & a_{1,3}\\ 0 & 0 & a_{2,2} & a_{2,3} \end{bmatrix} $, $ X= \begin{bmatrix} x_{0} & 0 & 0 \\ x_{1} & x_{0} & 0 \\ x_{2} & x_{1} & x_{0} \\ x_{3} & x_{2} & x_{1} \end{bmatrix} $, $ \textbf{x}= \begin{bmatrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} $, $ \textbf{b}= \begin{bmatrix} b_{0} \\ b_{1} \\ b_{2} \\ \end{bmatrix} $
To check a solution, given:
$ A= \begin{bmatrix} 1 & 2 & 3 & 4\\ 0 & 5 & 6 & 7\\ 0 & 0 & 8 & 9 \end{bmatrix} $, $ \textbf{b}= \begin{bmatrix} 30 \\ 38 \\ 26 \\ \end{bmatrix} $,
one possible solution is $ \textbf{x}= \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} $ and $ X= \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 2 & 1 \\ 4 & 3 & 2 \end{bmatrix} $ .