Feasibility of Exact Matching

Why Feasibility Is More Than Solving Equations

Exact cash-flow matching means that a portfolio’s cash receipts equal the liability payments at every relevant date. The earlier material on representing liabilities as dated cash flows and exact cash-flow matching provides the setup: list the dates, record each asset’s payment on each date, and compare the portfolio with the liability vector. The feasibility question is whether the available securities can do this using nonnegative holdings.

That last condition matters. An unrestricted system of equations may have a solution that requires holding a negative amount of a security. Such a solution is algebraically valid but does not describe a portfolio made only from purchases of the available securities. Feasibility therefore combines two tests: whether the liability vector is in the assets’ linear span, and whether it can be formed as a nonnegative combination of their cash-flow vectors.

Throughout this tutorial, cash flows are deterministic and known, with no mortality contingency or random distribution. A holding is the number of units of a security, and each security’s listed cash flows are per unit. The analysis is made directly in cash amounts at each date, so it does not require a valuation interest rate or discounting. It assumes the securities can be held in any nonnegative quantity and sets aside transaction costs, taxes, and other portfolio constraints.

Definition: For $m$ liability dates and $n$ available securities, let $A$ be the $m \times n$ cash-flow matrix. Entry $A_{tj}$ is the cash flow from one unit of security $j$ at date $t$. Let $b$ be the $m$-component liability vector and $x$ the $n$-component vector of security holdings. Exact matching requires $Ax=b$ and $x_j \ge 0$ for every security $j$.

The Linear System and Its Two Feasibility Tests

Each row of $Ax=b$ is a date-specific cash-flow equation. Each column of $A$ is one available security’s entire dated payment stream. If a security pays nothing on a date, its matrix entry in that row is zero. All entries in a row and the corresponding liability amount must use the same monetary unit.

The rank of $A$ measures the dimension of the linear span of its columns. If the rank is less than the number of dates, the assets cannot produce every possible liability vector, even if negative holdings were permitted. A particular liability vector can still be matched, however: it must lie in the column space of $A$. If the rank equals the number of dates, every liability vector has some real-valued solution to the equations, but that solution may require negative holdings.

Theorem: A liability vector $b$ can be exactly matched with nonnegative holdings if and only if it belongs to the cone generated by the columns of $A$. In other words, there must be numbers $x_1,\ldots,x_n$, all nonnegative, such that $b=x_1A_{\cdot 1}+\cdots+x_nA_{\cdot n}$, where $A_{\cdot j}$ denotes column $j$ of $A$.

The cone condition follows directly from the portfolio equation: multiplying column $j$ by $x_j$ scales that security’s cash flows, and adding the scaled columns gives the portfolio’s total cash flows. The coefficients must be nonnegative because they are holdings. Thus, being in the column space is a necessary algebraic condition, while being in the nonnegative cone is the full portfolio-feasibility condition.

When the system has no nonnegative solution, a useful diagnostic is a separating vector $y$. If every available column satisfies $y^{T}A_{\cdot j}\ge 0$, then every nonnegative portfolio must satisfy $y^{T}Ax\ge 0$. Consequently, if $y^{T}b<0$, the liability vector cannot be matched. This test can establish infeasibility without trying to enumerate possible portfolios.

Align the dates and units.
Use one row per liability date, include zero payments where appropriate, and keep every amount in the row in the same unit.

Build $A$ and $b$.
Put the per-unit cash flows of each available security in a column of $A$, and put the liability amounts in $b$.

Check linear consistency.
Use the rank or equations to see whether $b$ is in the column space of $A$. If not, no holdings, even unrestricted ones, can match it.

Impose nonnegativity and verify.
Find a solution with every holding nonnegative, then multiply through date by date to confirm the portfolio cash flows equal $b$.

Worked Feasibility Checks

Worked Example: A Full-Rank System with a Nonnegative Match

Three liabilities are due at times 1, 2, and 3, in that order, with amounts $\$75$, $\$125$, and $\$100$. Three available securities have the following cash flows per unit at those dates: security 1 pays $\$100$ at time 1 only; security 2 pays $\$100$ at time 2 only; security 3 pays $\$50$ at each of times 1 and 2 and $\$100$ at time 3. Determine whether exact matching is feasible. Amounts are deterministic; no interest rate or mortality assumption is needed.

Method. Use cash flows in hundreds of dollars, so the liability vector is $b=(0.75,1.25,1)^T$. The columns of the cash-flow matrix are the three securities’ per-unit cash flows:

A= \begin{pmatrix} 1&0&0.5\\ 0&1&0.5\\ 0&0&1 \end{pmatrix}, \qquad Ax=b.

The system gives $x_3=1$ from the third row. The first row then gives $x_1+0.5(1)=0.75$, so $x_1=0.25$. The second row gives $x_2+0.5(1)=1.25$, so $x_2=0.75$. All three holdings are nonnegative.

Check. At time 1 the portfolio pays $1(0.25)+0(0.75)+0.5(1)=0.75$, or $\$75$. At time 2 it pays $0(0.25)+1(0.75)+0.5(1)=1.25$, or $\$125$. At time 3 it pays $0(0.25)+0(0.75)+1(1)=1$, or $\$100$. The match is feasible. The matrix has full rank because its determinant is $1$, but the nonnegative holdings still need to be checked rather than inferred from rank alone. The common mistake avoided here is treating the half-unit payments from security 3 as if they occurred only at the final date.

Worked Example: Rank Deficiency and an Inconsistent Liability Vector

At three dates, two available securities pay, in hundreds of dollars, $c_1=(1,1,0)^T$ and $c_2=(0,0,1)^T$. A liability vector is $b=(1,2,1)^T$, also in hundreds of dollars. Determine whether any holdings can match it, even if negative holdings were allowed. The cash flows are deterministic, with no interest or mortality assumption.

Method. Form the matrix with one security per column:

A= \begin{pmatrix} 1&0\\ 1&0\\ 0&1 \end{pmatrix}, \qquad Ax= \begin{pmatrix} 1\\2\\1 \end{pmatrix}.

The first two rows require $x_1=1$ and $x_1=2$, respectively. These equations contradict each other. Equivalently, every vector in the column space of $A$ has equal first and second components, but $b$ does not. The two columns are independent, so $\operatorname{rank}(A)=2$, less than the three liability dates. No unrestricted solution exists, and therefore no nonnegative solution exists either.

For comparison, if the liability vector were instead $(1,1,1)^T$, the equations would give $x_1=1$ and $x_2=1$, a feasible match. Rank deficiency does not itself mean every liability is infeasible; it means liabilities must satisfy the restrictions imposed by the column space. The common mistake avoided is concluding that rank below the number of dates rules out every possible match.

Worked Example: Full Row Rank but No Nonnegative Match

Two liability dates are under consideration. Three securities have per-unit cash-flow vectors, in thousands of dollars, $c_1=(2,1)^T$, $c_2=(1,2)^T$, and $c_3=(3,3)^T$. The liability vector is $b=(1,0)^T$. Decide whether the liabilities can be exactly matched with nonnegative holdings. Cash flows are deterministic and no interest or mortality assumption is required.

Method. The matrix and equations are

A= \begin{pmatrix} 2&1&3\\ 1&2&3 \end{pmatrix}, \qquad \begin{aligned} 2x_1+x_2+3x_3&=1,\\ x_1+2x_2+3x_3&=0. \end{aligned}

The first two columns are independent because their $2 \times 2$ determinant is $2(2)-1(1)=3$, so $A$ has full row rank. Therefore an unrestricted real-valued solution exists for every two-date vector. But the second equation’s left side is a sum of nonnegative terms when $x_1,x_2,x_3\ge 0$; it cannot equal zero unless all three holdings are zero. That would make the first equation’s left side zero, not one. There is no nonnegative solution.

The same conclusion follows from a separating vector $y=(-1,2)^T$. Its dot products with the asset columns are $y^Tc_1=0$, $y^Tc_2=3$, and $y^Tc_3=3$, all nonnegative. But $y^Tb=-1$. Every nonnegative portfolio has a nonnegative dot product with $y$, whereas the liability vector has a negative one; they cannot be equal. The common mistake avoided is assuming full row rank alone guarantees a portfolio that can be purchased without short holdings.

What the Feasibility Result Does—and Does Not—Establish

A feasible solution establishes that the listed securities can reproduce the specified cash flows at the listed dates under the stated assumptions. It does not establish that the portfolio is cheapest, that the securities are actually available in the required quantities, or that cash flows between the listed dates match. Those are additional questions about the setting and constraints, not consequences of the linear system.

If the columns are linearly dependent, a liability may have several distinct matching portfolios. This can happen when securities have identical or redundant cash-flow patterns. Conversely, a unique algebraic solution is not automatically feasible: its holdings must still satisfy $x_j\ge 0$. In an exam problem, keep these questions separate:

Consistency: Does at least one real vector $x$ solve $Ax=b$?
Portfolio feasibility: Does at least one such solution also have every component nonnegative?
Verification: Does the proposed portfolio reproduce every liability amount at its date?

This matrix-and-cone perspective is aligned with the SOA Exam FM (Financial Mathematics) syllabus. A reliable conclusion should state which condition was checked: a rank or consistency failure rules out even unrestricted matching, while a nonnegative-cone failure rules out a purchase-only portfolio even when the equations are consistent.

Key takeaway: Exact matching with nonnegative holdings is the equation $Ax=b,\ x\ge0$. Rank and column-space checks identify linear restrictions, but the decisive portfolio test is whether the liability vector lies in the cone generated by the available securities’ cash-flow columns.

Check Your Understanding

For each problem, use cash-flow vectors in the stated units and decide whether the liability vector can be matched with nonnegative holdings.

At two dates, securities have vectors $c_1=(1,0)^T$ and $c_2=(0,1)^T$. The liability vector is $(2,3)^T$. Find a matching holding vector. (Answer: $x=(2,3)^T$; both holdings are nonnegative.)
At three dates, securities have vectors $c_1=(1,1,0)^T$ and $c_2=(0,0,1)^T$. For liability vector $(2,2,3)^T$, find holdings or explain why none exist. (Answer: $x=(2,3)^T$; the three date totals are $2,2,3$.)
Use the same securities as in question 2, but let the liability vector be $(2,1,3)^T$. Is it feasible, even with unrestricted holdings? (Answer: No; every vector in the column space has equal first and second components, while the liability vector does not.)
At two dates, three securities have vectors $c_1=(1,0)^T$, $c_2=(0,2)^T$, and $c_3=(1,1)^T$. The liability vector is $(2,3)^T$. Describe all nonnegative matching holdings. (Answer: $x_3=t,\ x_1=2-t,\ x_2=(3-t)/2$, where $0\le t\le2$.)
At two dates, available securities have vectors $c_1=(2,1)^T$ and $c_2=(1,2)^T$, and the liability vector is $(1,0)^T$. The columns have rank 2. Does full row rank make this match feasible? (Answer: No; the second-date equation $x_1+2x_2=0$ forces both nonnegative holdings to zero, which cannot produce the first-date liability of 1.)

What You'll Learn