quote

# S-EQA: Tackling Situational Queries in Embodied Question Answering

Vishnu Sashank Dorbala  Prasoon Goyal  Amazon Alexa AI  Robinson Piramuthu
Amazon Alexa AI  Michael Johnston  Amazon Alexa AI
Dinesh Manocha  Reza Ghanadan  Amazon Alexa AI

###### Abstract

We present and tackle the problem of Embodied Question Answering (EQA) with
Situational Queries (S-EQA) in a household environment. Unlike prior EQA work
tackling simple queries that directly reference target objects and
quantifiable properties pertaining them, EQA with situational queries (such as
“Is the bathroom clean and dry?”) is more challenging, as the agent needs to
figure out not just what the target objects pertaining to the query are, but
also requires a consensus on their states to be answerable. Towards this
objective, we first introduce a novel Prompt-Generate-Evaluate (PGE) scheme
that wraps around an LLM’s output to create a dataset of unique situational
queries, corresponding consensus object information, and predicted answers.
PGE maintains uniqueness among the generated queries, using multiple forms of
semantic similarity. We validate the generated dataset via a large scale user-
study conducted on M-Turk, and introduce it as S-EQA, the first dataset
tackling EQA with situational queries. Our user study establishes the
authenticity of S-EQA with a high $97.26\%$ of the generated queries being
deemed answerable, given the consensus object data. Conversely, we observe a
low correlation of $46.2\%$ on the LLM-predicted answers to human-evaluated
ones; indicating the LLM’s poor capability in directly answering situational
queries, while establishing S-EQA’s usability in providing a human-validated
consensus for an indirect solution. We evaluate S-EQA via Visual Question
Answering (VQA) on VirtualHome, which unlike other simulators, contains
several objects with modifiable states that also visually appear different
upon modification _—_ enabling us to set a quantitative benchmark for S-EQA.
To the best of our knowledge, this is the first work to introduce EQA with
situational queries, and also the first to use a generative approach for query
creation. Our work introduces a new task and approach that aims to improve the
usability of embodied agents in real-world household environments.

Figure 1: Simple vs Situational EQA: We propose and evaluate a Situational
Embodied Question Answering task. In contrast to simple queries that are
directly answerable by object properties, situational queries require the
inspection of multiple objects and consensus knowledge of their states. Our
approach uses an LLM to approximate this consensus and generate S-EQA, a
dataset of situational queries, with corresponding consensus object states and
relationships. S-EQA is validated via a large-scale user study, where we
establish the authenticity of the generated queries and consensus object data.
We observe the LLM’s poor capability in directly answering situational
queries; this establishes S-EQA’s usability as a key prior in providing human-
validated consensus data to simplify answering situational queries. Finally,
we evaluate S-EQA via Visual Question Answering (VQA) on VirtualHome,
quantitatively inferring S-EQA’s utility while also setting a benchmark.

##  I Introduction

Embodied Question Answering (EQA) introduced by Das. et. al., [1] involves an
agent exploring its surroundings to find an answer to a query. Prior work on
this task [2, 3, 4, 5] has primarily dealt with what we term “simple queries”,
that are directly answerable from states or properties of objects from the
simulator. For instance, questions like “What is the color of the sofa?” or
“Is there an object nearby to help me cut vegetables?” are directly related to
an object present in the environment, requiring a mix of vision-language
grounding with elementary commonsense to solve the task. While important, this
type of question-answering capability does not add much utility to a real-
world household robot, as the user asking questions is likely to already know
answers to simple questions about their surroundings.

Dataset |  Navigation + QA |  Multi-Target |  Interaction |  Abstract Queries |  Object State Consensus |  Query Creation
---|---|---|---|---|---|---
EQA [1] |  ✓ |  - |  - |  - |  - |  Rule-Based
MT-EQA [4] |  ✓ |  ✓ |  - |  - |  - |  Rule-Based
IQA [5] |  ✓ |  ✓ |  ✓ |  - |  - |  Rule-Based
K-EQA [6] |  ✓ |  ✓ |  - |  ✓ |  - |  Rule-Based
S-EQA (Ours) |  ✓ |  ✓ |  - |  ✓ |  ✓ |  Generative
TABLE I: Comparison of S-EQA with existing EQA datasets. We are the first to
propose situational queries that can be answered only by taking consensus
states of target objects into account. K-EQA [6] and our work address abstract
queries where necessary objects and properties for response are implied rather
than directly stated and necessitate an inference from the scene. For
instance, a K-EQA query _—_ “Is there an object used to cut food nearby?”
would answer Yes if a “knife” or a similar object was nearby. S-EQA further
extends this with situational queries requiring a consensus on object states.
For example, answering the query “Is the kitchen ready for meal preparation?”
requires estimating readiness based multiple objects and states _—_ Knives:
Present, Oven: Preheated, etc. As gathering real-world data for this type of
consensus is not readily available, we use an LLM to approximate it, and
verify it’s authenticity via a user study. As such, we are the first to
propose a generative approach to creating queries for an EQA dataset.

In contrast, answering queries such as “Is the kitchen ready for meal
preparation?” requires a sense of situational awareness in gauging the status
of multiple objects in the environment. While not uniformly defined, a
consensus does exist on standard conditions that can be used to answer such
questions. This refers to a set of generally accepted object states and
conditions (such as a Knife being Present) for successfully evaluating the
query. A household robot deployed in the real world is likely to encounter
such queries that require it to utilize consensus knowledge pertaining which
objects and associated states are commonly associated with the situation. We
term these as situational queries, and in this work, tackle the twofold
challenge of 1) conjuring authentic situational queries and corresponding
consensus object data and 2) highlighting the role of the consensus in
simplifying the process of responding to situational queries.

A query such as “Is the house ready for sleeptime?” is a situational query,
since there exist generally accepted object states, such as dimmed lights,
closed windows, locked doors, etc., which most people associate with a house
being ready for nighttime. However, a query like “Can I bring guests over?”,
while situational, is too ambiguous, as the answer relies on various unstated
factors and user preferences on household norms, and event-specific
constraints. For situational queries to be validatable, it is important for
them to not be too ambiguous so as to allow for a consensus to exist. Our work
places emphasis on this, and follows an in-context learning scheme on an LLM
to avoid overly simplistic nor excessively ambiguous queries.

Developing a dataset for EQA in the past has been limited to constructing
simple queries using entities from a simulator [4, 5], with some work
extending it to abstract queries built on scene-graphs [6]. Posing situational
queries using these existing techniques is however nontrivial, as they stem
from human intuition and contextual awareness of the environment. Setting up
real-world experiments to collect this data is also cumbersome; if not having
an intrusive agent capturing conversations at home, an offline approach would
be cognitively heavy, requiring humans to come up with queries for imaginary
situations. As such, in our work, we use an LLM to generate and study such
queries, while ensuring they cover unique concepts stemming from various
situations. Table I compares our dataset with existing ones.

Main Results: To tackle these issues, we leverage the commonsense capabilities
of Large Language Models (LLMs) and present an approach to generate
situational queries and associated consensus object states and relationships.
LLMs allow us to generate situational query data for a variety of scenarios
which are nontrivial to obtain via real-world data collection. The main
contributions of our work are as follows:-

  * •

We propose a novel Large Language Model (LLM)-based method for generating
Situational Queries for Embodied Question Answering (EQA). Unlike simple
queries that directly reference particular objects, situational queries
necessitate an understanding of the consensus objects and states pertaining a
situation.

  * •

Our proposed Prompt-Generate-Evaluate (PGE) scheme wraps around an LLM to
generate a wide array of unique and challenging queries covering various
household scenarios. Along with the queries, we also generate corresponding
consensus object information, pointing to object states and relationships
relevant to the queries.

  * •

The generated queries are validated via a large scale MTurk [7] user study to
produce S-EQA, a LLM-generated dataset containing $2000$ situational queries,
associated consensus object data, and predicted answers. While the number of
queries is small due to their highly abstract nature, PGE ensures diversity in
the queries across rooms.

  * •

We quantitatively evaluate S-EQA by performing Visual Question Answering (VQA)
on VirtualHome images with both situational queries (Room VQA) and consensus
data (Object VQA) to establish a benchmark.

  * •

We observe that 97.26% of users find the generated queries to be answerable
provided the consensus data, while only 46.2% of user answers align with the
LLM predicted ones. From the former, we can infer the authenticity of LLM
generated data in producing human-like consensus states, while the latter
indicates the LLM cannot be used to directly answer situational queries;
establishing the need and use-case for S-EQA, a human-validated dataset that
provides situational queries along with consensus objects and states.

Figure 2: Prompt-Generate-Evaluate (PGE) Scheme: We utilize an LLM (GPT-4) to
generate situational datapoints comprised of queries, corresponding consensus
object states, relationships, and expected answers. This data generation
occurs over m iterations, refining LLM prompts after evaluating every batch of
n datapoints. For each batch, BERT embeddings of the $n$ queries are computed
and denoted as $Emb(Q_{n})$. A cosine similarity $\mathbbm{C}$ is then
computed between $Emb(Q_{n})$ and $Emb(\mathbbm{Q}_{S})$, the embeddings of
existing queries in the Situational Query Database $\mathbbm{Q}_{S}$. The
cosine similarity $\mathrm{C}$ is used to determine if the generated queries
are sufficiently different from those in the database and if not, we continue
conversation with the LLM (indicated with the red arrows). Concurrently, we
cluster $Emb(\mathbbm{Q}_{S})$ into k categories, selecting the query nearest
to the centroid in each cluster for feedback, labeled as “Generated Queries”
in the System Prompt (denoted by blue arrows). The ideal datapoint generation
pathway is highlighted by the green arrows.

##  II Related Work

Embodied Question Answering (EQA): EQA is a popular task [8, 5, 9] that
involves a robot attempting to answer a query by exploring and gathering
information from its surroundings. It was introduced by Das et. al [1] as a
single-target question-answering dataset. Yu et. al. [4] further extended this
task to a multi-object setting, MT-EQA, where correspondences between multiple
target objects present in the question itself need to be analyzed before
arriving at an answer. Both these works use a template-based approach to
generating questions, and this was deemed sufficient since the queries are
objective in nature mentioning the objects of interest in their query itself.
This however is a limitation, since a majority of queries tend to be
subjective or situational in nature [10], especially in a household
environment.

Sintean et. al in K-EQA [6] attempt to tackle this problem, by using scene-
graph data and formal grammar to postulate queries. However, these queries are
still limited to simple object grounding within a scene, and do not require
any form of situational awareness about the readiness of an environment. For
instance, S-EQA considers queries like “Is the living room ready for a movie
night?”, and presents consensus multiple object states (TV: On, Popcorn:
Cooked, On Table, etc.) to measure this readiness. For the same example, a
K-EQA query would have been constructed as “Is there a device for watching
movies in the living room?”, which requires only scene knowledge for an
answer, but does not require situational knowledge about the consensus states
of objects for a movie night.

In our work, we utilize an LLM to generate situational queries and approximate
human consensus on object states required to answer the query. Our queries are
an abstraction above the scene-knowledge based K-EQA queries, requiring
consensus knowledge about multiple object states for validation.

LLMs for Query Generation: A recent trend has seen the emergence of Large
Language Models (LLMs) such as GPT-3.5 [11], GPT-4 [12], LLaMA [13], Palm [14]
and Palm-e [15]. These models are well known for their commonsense reasoning
capabilities [16], especially in the context of question-answering. In
embodied AI, these capabilities have recently been leveraged to produce
superior planning and decision-making strategies during navigation [17, 18,
19, 20]. In our case, we wish to generate situational queries for embodied
question answering, which as defined in Section I require consensus about
object states and relationships in the environment. As such, we are motivated
to use LLMs for generating these queries and ask if their commonsense
reasoning capabilities can sufficiently represent the consensus needed to
answer situational queries.

##  III Situational EQA: Generation, Analysis, and Evaluation

Having motivated the problem of Situational EQA, we now present a detailed
description of our approach. We present three phases _—_ generating
situational data using LLMs, validating this data via segregation and a user
survey, and finally evaluating it on the VirtualHome simulator. We hope the
generative approach being used to develop S-EQA helps foster future research
in this domain.

###  III-A Situational Query Definition

Situational queries in our work are defined as questions requiring the
assessment of a collection of consensus objects and states to reach an
existential ‘Yes/No’ answer. For example, a query such as “Is the livingroom
ready for movie night?” has a Yes/No answer based on whether consensus objects
like the TV, lights, etc. are in their appropriate state. Additionally, we
want to ensure that the queries are related to a situation and are not simple
in nature, i.e., the target objects and states are not in the query itself.
For example, “Is the sofa blue?” [1] or “How many objects can be used to hold
rice?” [6] are simple queries, as they do not deal with a situation, but
rather pose a query referencing objects in the environment. In contrast, “Is
the dining area set up for dinner?” is situational, as it doesn’t explicitly
mention any objects, but requires the identification of relevant objects (eg.
table, napkins), and a consensus on what their states should be (open,
present) for the answer. Considering the LLM as a function $\mathcal{L}$ that
generates queries $q$, and $\mathbbm{Q}$ to be a set of all possible queries
generated by $\mathcal{L}$, we want situational queries
$\mathbbm{Q}_{S}\subset\mathbbm{Q}$, which satisfies the following conditions
-

  * •

The query must not directly reference any object, i.e., it must omit words
from a set $\mathbb{W}$ which includes “object”, “table”, “chair”, etc.

  * •

The query must be a question.

  * •

The answer to the query must be binary i.e., Yes/No, and not subjective in
nature.

Formally, we can define $\mathbbm{Q}_{S}$ as:

$\displaystyle\mathbbm{Q}_{S}=\\{$ $\displaystyle
q\in\mathbbm{Q}\mid\text{OmitWords}(q,\mathbbm{W})$
$\displaystyle\land\text{Question}(q)\land\text{BinaryAnswer}(q)\\}$ (1)

This formulation ensures that $\mathbb{Q}_{s}$ consists only of queries that
are abstract, questioning in form, and expect a binary Yes/No response. We
present these conditions as in-context rules to the LLM to curate it’s
responses.

###  III-B Generating Situational Queries: S-EQA

Figure 2 presents an overview of our generation approach. We generate
datapoints of the format - [Situational Query, Object-States, Object-
Relationships, LLM Answer]. A sample datapoint is as follows -

> Query: “Is the bathroom ready for a shower?”
> Object-States : [lightswitch: [‘On’], towels: [‘Present’], Soap: [‘Present’]
> …]
> Object-Relationships : [lightswitch inside bathroom, towels inside bathroom,
> … ]
> LLM Answer: ‘Yes’
>

Here, the LLM points to a set of object states and relationships (such as
‘towels inside bathroom being present’) that it believes need to be checked to
determine if the bathroom is ready for a shower. We also predict an answer to
the query that is later verified in our user study.

####  III-B1 VirtualHome Setup

We use the VirtualHome [21] simulator for defining ground truth objects,
states and properties in our experiments. It contains 7 different household
environments containing over 390 objects. Unlike other embodied simulators,
VirtualHome is unique in that it contains several household objects including
interactable ones, with easily modifiable locations and states. The objects
are also visually different upon modification, and this allows us to perform
VQA later on to evaluate our dataset.

All objects in VirtualHome have a set of state properties, which are either
physical Open/Closed (eg. for a Door), and/or On/Off (such as lights) or
Present/None (such as Apple). These objects also have a relationship with
either the room or another object. For example, Apple INSIDE Fridge and Fridge
INSIDE livingroom are both valid relationships. The simulator has 4 different
rooms into which all objects are placed - [livingroom, bedroom, kitchen,
bathroom]. We use these room markings to group and analyze the generated
queries later on.

(a) Room Categories

(b) Situational Categories

(c) Spatio-Temporal Categories

Figure 3: t-SNE plots of S-EQA: We categorize and analyze the generated data
in 3 aspects. For Room categories, we observe that most of the generated
datapoints ($83.5\%$) belong to a particular room, suggesting that the LLM
tends to create room-specific queries as opposed to multi or no-room
scenarios. For Situational Categories, we observe that $82.20\%$ of the data
generated is situational according to our definition. For Spatio-Temporal
Categories, we look at whether the questions can be answered by only using the
spatial positioning of objects and infer that $77.96\%$ of the queries are
spatial.

####  III-B2 Prompt-Generate-Evaluate (PGE) Scheme

Figure 2 presents an overview of our Prompt-Generate-Evaluate scheme for
generating data. We perform analytical operations on the LLM’s generated
datapoints to ensure they fit into our definition of situational queries,
while also maintaining diversity. The System Prompt for our LLM contains a
list of all object states and relationships. We also provide additional rules
and in-context examples to improve the generation of prompts. For instance,
explicitly mentioning “Do not conjure any new object states” ensures that the
generated datapoints do not contain states that are not achievable in
VirtualHome. Additionally, we also provide a set of $k$ “Generated Queries” as
feedback to the system prompt. These represent queries that the LLM has
already generated, and in the User prompt, encourage the LLM to generate
queries different from these. Our strategy for choosing these queries is
discussed in the feedback measures presented below.

Our User Prompt asks to generate $n$ datapoints in the format specified
earlier, and provides a few sample datapoints. We also provide some in-context
rules to ensure that the generated queries are not too simplistic, not too
ambiguous, and are also unique. For instance, we explicitly state ‘The
situational query must not reference any object or even contain the word
‘object’.’ and ‘The query must have a Yes/No answer.’. Additionally, we ask it
to generate queries very different from what is already present in the $k$
Generated Queries in the System Prompt, to avoid simple sentence rephrasing.

To ensure that our Situational Query Database $\mathbbm{Q}_{S}$ contains data
points that adhere to the specifications presented above, we take the
following two feedback measures:

  * •

After generating $n$ data points, we embed the situational queries using
RoBERTa [22] to get sentence embeddings $Emb(\mathbbm{Q}_{S})$. We perform
agglomerative clustering [23] on $Emb(\mathbbm{Q}_{S})$ to accumulate them
into $k$ groups of queries based on sentence similarity. We then pick the
query closest to the centroid of each of these clusters to get $k$ queries
that best represent the diversity in the generated data. Finally, we update
the system prompt with these queries.

  * •

Simultaneously, we compute the cosine similarity $\mathrm{C}$ of the $n$
generated query embeddings $Emb(Q_{n})$ with the queries already present in
the Situational Query Database $\mathbbm{Q}_{S}$. If $\mathrm{C}$ is greater
than a particular threshold ($X$), we continue the “conversation” with the
LLM, by presenting it with a re-generation prompt. We mention the percentage
of similarity, and ask the LLM to re-generate a new batch of datapoints.

These feedback measures ensure $\mathbbm{Q}_{S}$ contains unique situational
queries that are not simple rewordings, while also encouraging diversity in
the generated situations.

The total number of datapoints generated $\mathbbm{Q}_{S}$ is always less than
or equal to the product of the looping parameters $n$ and $m$, i.e.,
$\mathbbm{Q}_{S}\leq n*m$. While our approach allows for the generation of
potentially infinite datapoints, we observe a saturation point where the LLM
starts to generate similar-looking queries (“Is the bathroom clean and dry?”
vs “Has the bathroom been cleaned today?”). This is indeed a drawback of such
a generative approach, and can be attributed to the abstract nature of the
queries being generated, which do not pertain a particular object, but related
to a household situation. Therefore, to effectively assess the utility of the
data, we cut off generation at $2000$ data points. We validate this data via a
large-scale MTurk user study, and present this as S-EQA, a dataset containing
diverse and challenging situational queries along with consensus object data
to help answer them.

###  III-C Validating S-EQA: t-SNE Plots and MTurk Survey

Our objective with validating S-EQA is not just to measure the authenticity of
the generated data, but also to establish necessity and the real-world
usability of our dataset. First, we first visualize the queries in
$\mathbbm{Q}_{S}$ using t-SNE plots to analyze their diversity. We then
conduct a Mechanical Turk based user study to validate the generated data.

####  III-C1 Analyzing S-EQA with t-SNE

Figure 3 illustrates $3$ t-SNE plots we derive from $Q_{S}$. These are as
follows -

Room Categorization: Using the room properties obtained from VirtualHome
(section III-B1), we group the questions into 6 categories - [kitchen,
livingroom, bedroom, bathroom, multi-room, no room] (Ref. Fig. 3(a)). We infer
from this plot that most questions being generated belong to one particular
room, as opposed to multiple ones. This suggests that the LLM tends to
generate situational queries that are usually room-specific, referring to
multiple objects in a single area. As such, multi-room scenarios (like “Is the
house ready for sleeptime?”) are less common in the generated data.

Situational Categorization: Here, we use the LLM as a classifier to predict if
the generated questions are situational according to our definition in III-A.
We prompt and present in-context examples accordingly. We notice that $82.2\%$
of generated questions (Ref. Fig. 3(b)) are classified as situational
according to the LLM. As the LLM classifications have several false positives,
this result motivates us to use human-validation to authenticate the dataset.

Spatio-Temporal Categorization: Here, we use the LLM to categorize the
generated queries as spatial or temporal. Temporal questions rely on time-
sensitive knowledge about a dynamic environment (Refer Fig. 3(c)). For
instance, a query like “Was someone sleeping in the bedroom today?” is
temporal, as it requires knowledge of past environmental states to be
answerable. Conversely, a query like “Is the kitchen ready for cooking?” is
spatial, as it requires the agent to gauge only current states. We observe
that $77.96\%$ of the generated questions are Spatial ones, showing that PGE
prefers modeling spatial relations over temporal ones.

####  III-C2 Assessing S-EQA’s Utility with MTurk

We conduct a large-scale Mechanical Turk [7] study to gauge S-EQA’s
authenticity and usability in answering real-world queries.

In our first experiment, we assess whether the consensus object data being
generated adequately facilitates answering situational queries. Workers are
shown a query, images of the corresponding room, and images of objects set to
consensus states, while the LLM Answer remains hidden to negate bias. Given
options of Yes, No, and Cannot Answer, a worker’s capacity to give a
definitive response, i.e., choosing Yes or No, serves as an indicator of
whether the generated data is in alignment with general user consensus. For
instance, the query “Is the house ready for sleeptime?”, if unanimously agreed
upon by workers when shown images of dimly-lit rooms, closed doors, and
windows, validates the data point.

Subsequently, in a second experiment, workers are presented with an image of a
room accompanied by a situational S-EQA query (For eg. Is someone working in
the bedroom? with top-views of the bedroom) and, separately, images of
consensus objects paired with simpler, objective queries about their state
(For eg., Is the Computer On? with an image of a computer being on). For the
simple query annotation, we additionally sample ‘Yes/No’ questions the SimVQA
[24] dataset to even out the number of situational and simple queries. An
improved annotator performance in simple over situational queries would
indicate S-EQA’s real-world usability in providing human-authenticated
consensus object-states for situational queries which are relatively simpler
to answer.

Figure 4: Room and Object VQA: We perform two types of VQA using the S-EQA
dataset. In this example, the situational query asks if someone could be
working in the bedroom. The room images of the scene obscure the view of the
computer, leading to a negative prediction. On the other hand, the Object VQA
directly analyzes the state of the consensus objects in the datapoint, leading
to a positive prediction that aligns with the user-study outcome for this
example. Note that this outcome however doesn’t align with the LLM’s Answer,
and this is true with 46.8% of cases in S-EQA. We infer from this the LLM’s
poor answering capability on situational queries, highlighting the need for a
breakdown on consensus-objects provided by S-EQA. The superior performance of
the Object VQA over Room VQA (See Table II) further suggests that knowing the
consensus data can simplify answering situational queries. Our second user
study corroborates this with 97.04% of participants being able to answer
simple queries (Object VQA) over just 62.29% being able to answer situational
ones (Room VQA). This highlights an important utility of S-EQA in indirectly
answering complex situational queries by reframing them as a set of simpler
objective queries about consensus objects.

###  III-D Evaluating S-EQA in VirtualHome

Assuming low-level navigation to be solved, we quantitatively evaluate S-EQA
via Visual Question Answering (VQA). VirtualHome provides us with a household
environment where object states visually change upon modifying states. We
present VQA models with the same setup as described in our first MTurk
experiment presented in III-C2, and compare the results. Figure 4 presents an
overview.

Room VQA (Situational Query): Here, we present the VQA model with multiple
top-view images of a relevant room as input, and ask it to answer the
associated situational query with Yes/No/Cannot Answer. Most of our queries
are associated with one particular room (see Figure 3(a)), which is often part
of the query itself. During our experimentation, we observed a clear bias in
model performance with such queries. For instance, if the query contained
‘living room’, and the image was that of the living room, the answer would
always be yes, irrespective of the actual context of the query. To mitigate
this, we replace any mention of a room in the query with the generic term -
“this place”.

Object VQA (Simple Query): Here, we use consensus object states linked with
the situational query to formulate simple objective questions for a VQA model.
These are of the form -

> Is the $<$OBJECT$>$ $<$STATE$>$?

We provide the VQA model with questions along with images of the consensus
objects in their designated states.

For both Room VQA and Object VQA, we measure the accuracy and F1-scores of
prediction across all the images, using the human-verified answers as ground
truth. We use a threshold of $0.5$ on the accuracy and F1 scores to determine
if the query has successfully been answered. Additionally, we also compute the
Joint Accuracy ($\mathrm{J}_{A}$), and Joint F1 ($\mathrm{J}_{F1}$) scores
which is a success case when either of the Room or Object VQA are successful.
Formally, let $R$ be the accuracy or F1 result for Room VQA and $O$ be the
same result for Object VQA, where $R,O\in\\{0,1\\}$. $R=1$ indicates a match
with the ground truth for Room VQA, and similarly, $O=1$ indicates a match for
Object VQA.

$\mathrm{J}$ is then defined as:

$\mathrm{J}(R,O)=\begin{cases}1&\text{if }R=1\text{ or }O=1\\\
0&\text{otherwise}\end{cases}$

$\mathrm{J}_{a}$ and $\mathrm{J}_{F1}$ give us an upper bound on the
performance of VQA models on S-EQA in VirtualHome. For $\mathrm{J}_{F1}$, we
set a threshold of $0.5$ above which the score would be deemed satisfactory.

##  IV Results and Inferences

We use GPT-4 [12] as the LLM of choice to generate situational queries in our
experiments. Our ablations with GPT-3.5 showed poor quality in terms of
generation, with many outputs not fitting into our specified datapoint format.

###  IV-A Preparing the Simulator

We first program the object states and relationships from the generated data
points into the VirtualHome environment. This also includes filtering out a
small subset of bad states which are not feasible. For instance, ‘computer
INSIDE fridge’ is not a valid relationship for us to set, and the simulator
prevents this.

For VQA and the MTurk user study, we require images of the room and
corresponding consensus objects set to their appropriate states. We gather
room images by considering the 4 corners of each room, with a camera pointing
downwards towards the center. Choosing images in this way allows us to achieve
maximum coverage of objects present.

Then for object images, we use the first-person view of a human placed in the
environment. The human is instructed to walk to each of the objects present in
a S-EQA datapoint, and we grab an image when they are present in front of
them. This approach for capturing images proved simpler to implement and is
in-line with the visual perspective of an agent grabbing an object.

###  IV-B Quantitative Results and Benchmark

We use BLIP-2 [25], BLIP [26] and ViLT [27], all finetuned on VQAv2 [28] to
evaluate S-EQA, and these results are presented in Table II.

| VQA Model |  Accuracy % $\uparrow$ |  F1-Score % $\uparrow$
---|---|---|---
Room |  BLIP-2 [25] | 42.31 | 52.51
BLIP [26] | $41.82$ | $49.63$
ViLT [27] | $39.80$ | $42.31$
Object |  BLIP-2 [25] | 58.26 | 68.75
BLIP [26] | $51.33$ | $63.75$
ViLT [27] | $47.27$ | $58.31$
Joint |  BLIP-2 [25] | 89.6 | $82.5$
BLIP [26] | $83.29$ | 83.75
ViLT [27] | $72.91$ | $80.35$
TABLE II: VQA performance on Room and Object VQA.

Observe the higher Object-VQA accuracies and F1 scores over Room-VQA across
each approach. This suggests that answering situational queries by looking at
images at a room level is significantly harder than answering simple queries
about the states of target objects. Our second MTurk experiment (Refer III-C2)
further corroborates this result, suggesting S-EQA’s usability in providing
the simpler consensus object data for answering situational queries.

The high values on joint scores $\mathrm{J}$ indicate an upper bound on
performance. While still better than RoomVQA, ObjectVQA models have mediocre
performance overall, despite the queries being simple. This can be attributed
to inference on synthetic images from VirtualHome, which these models have not
been trained on. Our real-world experiments suggest improved performance,
confirming this domain gap.

Figure 5: Distribution of Query Lengths

Figure 5 provides a distribution of the query lengths in S-EQA. Note that this
distribution resembles a Gaussian, with the median character count of queries
being around $40.2$, and word count being $7.7$. This indicates that most
generated queries in S-EQA are of an ideal length, with GPT-4 producing
queries with concise scenario-specific language as opposed to an accumulation
of multiple object states like MT-EQA [4].

###  IV-C Qualitative Results and Inference

In both our MTurk experiments (Refer III-C2), we measure average reviewer
agreement across 5 users on each question to obtain ground truth labels on the
data. For instance, if a question has $3$ Yes’s, and $2$ No’s, we label the
ground truth as ‘Yes’. On the other hand, if even one of the annotations is
‘Cannot Answer’, we label the human-annotated output by the same.

For the first experiment, we obtain a low ‘Cannot Answer’ percentage of
$2.74\%$ among the nearly $5\times 2K=10K$ participants. As such, a high
percentage ($97.26\%$) of generated queries being answerable strongly
indicates that the generated consensus object states are good representation
of the human consensus for each query. Conversely, a low correlation of
$46.2\%$ in LLM-generated and worker-annotated answers suggests the LLM’s
limited capability in adequately answering them. To analyze this further, we
attempt to reason about the generated answers by prompting GPT-4 to provide
reasoning:

> $<$Situational Query and Object Data$>$
> Your answer is: $<$LLM Answer (Yes/No)$>$.
> Can you provide a brief reason for your answer focusing only on the object
> states and relationships provided?

Upon inspecting the generated reasoning, we notice that GPT-4 often goes
against the consensus while predicting the answer. For example, consider the
following datapoint -

> Query: “Is the living room prepared for a movie night?”
> Object-States : [tv: [‘ON’], lights: [‘OFF’], remotecontrol: [‘ON’], …]
> Object-Relationships : [tv INSIDE livingroom, lights INSIDE livingroom,
> remotecontrol INSIDE livingroom, …]
> LLM Answer: ‘NO’
>

The reasoning generated for the LLM Answer is as follows -

> The lights are off which is suitable for a movie night, but the TV is on
> which is not suitable for movie watching as it may create distractions.

GPT-4 suggests that the TV being ON may create distractions for movie watching
and hence responds with No. However, a more plausible situation would be that
the user would watch the movie on the TV itself, and that the living room is
indeed prepared for a movie night.

On the flip side, since our object states are limited to the ones present in
VirtualHome, we are inclined to believe that the quality of the output depends
on the richness of the object set. In this example, for instance, additional
object information such as DVD: [‘Present’] and Popcorn ON Table would improve
the consensus of a movie night about to happen. Since such objects do not
exist in VirtualHome, it is reasonable to assume that GPT-4’s explanation is
sufficient.

In our second MTurk survey, we sought to assess the usability of S-EQA by
comparing situational and simple queries. For simple queries, $74.3\%$ of
participants answer accurately, indicating their mostly unambiguous and
straightforward nature. In contrast, S-EQA queries show only a $42.7\%$
accuracy. $37.71\%$ of users also choose Cannot Answer on the situational
queries, as opposed to $2.96\%$ on the simple ones. This discrepancy showcases
the usability of S-EQA in providing consensus objects and states for
indirectly answering situational queries.

We infer from these qualitative experiments that while GPT-4 is indeed capable
of producing situational queries and authentic consensus information, it often
goes against the norm in answering the query itself. As such, an agent
equipped with an LLM for directly answering situational queries from scene
images might not be able to do so correctly. S-EQA is very useful here, as it
simplifies the QA task by providing authentic objects and states relevant to
the situational query for the agent to ground and subsequently answer the
query.

##  V Conclusion, Limitations and Future Work

We tackle the novel and challenging problem of Embodied Question Answering
with Situational Queries. Unlike prior work that dealt with simple objective
queries pertaining target objects, situational queries necessitate an
approximation of a consensus on object states. We use a Large Language Model
(LLM), GPT-4 to approximate this consensus, incorporating it in an approach to
pose unique situational queries, corresponding consensus object information
and predicted answers. We use VirtualHome as an embodied simulation platform
for our experiments, as it provides us with modifiable object states that also
visually change in their appearance upon modification, allowing for
quantitative validation.

We validate the authenticity of the generated data via a large scale MTurk
user study with $10K$ participants, and introduce it as S-EQA, the first EQA
dataset addressing situational queries. In the study, we observe a low
$46.2\%$ correlation of the GPT-4’s answers with that of the user, and notice
a very high percentage of users ($97.26\%$) believe the queries are answerable
with the provided consensus states. This lets us infer that while GPT-4 is
capable of reliably generating consensus objects and states required for
answering a situational query, it is incapable of directly answering the
situational query itself. From this, we infer S-EQA’s usability, in providing
a human-verified dataset of consensus data that could be used as a prior to
break down situational queries into simpler, objective ones based on a human-
consensus to answer them in household environments. Further, we perform Room
and Object level VQA on S-EQA and quantitatively observe this discrepancy, and
setting a benchmark for validating S-EQA on VirtualHome.

As a future experiment, we will look at a real-world deployment of an S-EQA-
powered household robot, to gather data and finetune the LLM’s generational
capabilities. The queries in S-EQA are limited due to the abstract,
situational nature of the questions being generated and the limited number of
objects. Future work will explore cases when the user poses novel questions
outside the S-EQA dataset, requiring semantic alignment of the novel query
with those in the dataset to extract consensus objects and states for S-EQA.

## References

  * [1] A. Das, S. Datta, G. Gkioxari, S. Lee, D. Parikh, and D. Batra, “Embodied question answering,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 1–10.
  * [2] H. Luo, G. Lin, F. Shen, X. Huang, Y. Yao, and H. Shen, “Robust-eqa: robust learning for embodied question answering with noisy labels,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2023.
  * [3] D. Gao, R. Wang, Z. Bai, and X. Chen, “Env-qa: A video question answering benchmark for comprehensive understanding of dynamic environments,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 1675–1685.
  * [4] L. Yu, X. Chen, G. Gkioxari, M. Bansal, T. L. Berg, and D. Batra, “Multi-target embodied question answering,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 6309–6318.
  * [5] D. Gordon, A. Kembhavi, M. Rastegari, J. Redmon, D. Fox, and A. Farhadi, “Iqa: Visual question answering in interactive environments,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 4089–4098.
  * [6] S. Tan, M. Ge, D. Guo, H. Liu, and F. Sun, “Knowledge-based embodied question answering,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * [7] “Amazon Mechanical Turk — mturk.com,” https://www.mturk.com/.
  * [8] J. Duan, S. Yu, H. L. Tan, H. Zhu, and C. Tan, “A survey of embodied ai: From simulators to research tasks,” _IEEE Transactions on Emerging Topics in Computational Intelligence_ , vol. 6, no. 2, pp. 230–244, 2022.
  * [9] Q. Sima, S. Tan, H. Liu, F. Sun, W. Xu, and L. Fu, “Embodied referring expression for manipulation question answering in interactive environment,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 7635–7641.
  * [10] Y. Li, A. X. Feng, J. Li, S. Mumick, A. Halevy, V. Li, and W.-C. Tan, “Subjective databases,” _arXiv preprint arXiv:1902.09661_ , 2019.
  * [11] OpenAI, “Language models are unsupervised multitask learners,” _OpenAI Blog_ , vol. 23, no. 6, 6 2020, https://openai.com/blog/chatgpt.
  * [12] ——, “Gpt-4 technical report,” 2023.
  * [13] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar _et al._ , “Llama: Open and efficient foundation language models,” _arXiv preprint arXiv:2302.13971_ , 2023.
  * [14] A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann _et al._ , “Palm: Scaling language modeling with pathways,” _arXiv preprint arXiv:2204.02311_ , 2022.
  * [15] D. Driess, F. Xia, M. S. Sajjadi, C. Lynch, A. Chowdhery, B. Ichter, A. Wahid, J. Tompson, Q. Vuong, T. Yu _et al._ , “Palm-e: An embodied multimodal language model,” _arXiv preprint arXiv:2303.03378_ , 2023.
  * [16] J. Huang and K. C.-C. Chang, “Towards reasoning in large language models: A survey,” _arXiv preprint arXiv:2212.10403_ , 2022.
  * [17] V. S. Dorbala, J. F. Mullen Jr, and D. Manocha, “Can an embodied agent find your” cat-shaped mug”? llm-based zero-shot object navigation,” _arXiv preprint arXiv:2303.03480_ , 2023.
  * [18] G. Zhou, Y. Hong, and Q. Wu, “Navgpt: Explicit reasoning in vision-and-language navigation with large language models,” _arXiv preprint arXiv:2305.16986_ , 2023.
  * [19] D. Shah, B. Osiński, S. Levine _et al._ , “Lm-nav: Robotic navigation with large pre-trained models of language, vision, and action,” in _Conference on Robot Learning_. PMLR, 2023, pp. 492–504.
  * [20] C. H. Song, J. Wu, C. Washington, B. M. Sadler, W.-L. Chao, and Y. Su, “Llm-planner: Few-shot grounded planning for embodied agents with large language models,” _arXiv preprint arXiv:2212.04088_ , 2022.
  * [21] X. Puig, K. Ra, M. Boben, J. Li, T. Wang, S. Fidler, and A. Torralba, “Virtualhome: Simulating household activities via programs,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 8494–8502.
  * [22] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov, “Roberta: A robustly optimized bert pretraining approach,” _arXiv preprint arXiv:1907.11692_ , 2019.
  * [23] D. Müllner, “Modern hierarchical, agglomerative clustering algorithms,” _arXiv preprint arXiv:1109.2378_ , 2011.
  * [24] P. Cascante-Bonilla, H. Wu, L. Wang, R. S. Feris, and V. Ordonez, “Simvqa: Exploring simulated environments for visual question answering,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 5056–5066.
  * [25] J. Li, D. Li, S. Savarese, and S. Hoi, “Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models,” _arXiv preprint arXiv:2301.12597_ , 2023.
  * [26] J. Li, D. Li, C. Xiong, and S. Hoi, “Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 12 888–12 900.
  * [27] W. Kim, B. Son, and I. Kim, “Vilt: Vision-and-language transformer without convolution or region supervision,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 5583–5594.
  * [28] Y. Goyal, T. Khot, D. Summers-Stay, D. Batra, and D. Parikh, “Making the V in VQA matter: Elevating the role of image understanding in Visual Question Answering,” in _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.


We establish a factorisation theorem for invertible, cross-symmetric, totally nonnegative matrices, and illustrate the theory by verifying that certain cases of Holte's Amazing Matrix are totally nonnegative.

2020 Mathematics subject classification: 15B48
Keywords. Cross-symmetric matrix, centro-symmetric matrix,  totally nonnegative matrix

§ INTRODUCTION

In [7], Holte introduces an “Amazing Matrix" that arises in connection with carries that occur when adding integers. For each base $b$, he constructs an $n\times n$ matrix $P$ whose $(i,j)$-entry is the probablility that, when adding $n$ random numbers written in base $b$, the next carry will be $j$ given that the previous carry was $i$. Holte discovered many interesting facts about the amazing matrix, including the fact that $P$ is cross-symmetric (centro-symmetic in some sources); that is, it is radially symmetric about its centre.

In a later article [2], Diaconis and Fulman uncovered a connection between the amazing matrix and card shuffling. In their study of properties of the amazing matrix, they showed that when the base $b=2$ the matrix is totally nonnegative; that is, all minors are nonnegative. They also showed that in arbitrary base $b$ all of the $2\times 2$ minors are nonnegative, and they made the conjecture that the amazing matrix is totally nonnegative. As far as we are aware, this conjecture is still open. In [9], McMillan made some progress towards verifying that the conjecture holds.

There are efficient tests to determine whether or not a matrix is totally nonegative, for example, Neville elimination <cit.> or Cauchon's deletion algorithm [5].
However, these processes immediately destroy the desirable property of cross-symmetry. Our interest in the amazing matrix conjecture led us to construct the algorithm presented here which preserves cross-symmetry and checks for total nonnegativity. It leads to the factorisation theory that we present here: each invertible, cross-symmetric, totally nonnegative matrix can be factorised into a product of cross-symmetric “atoms” which are the cross-symmetric analogues of the elementary matrices that arise in the Neville factorisation theory.

Although we are not able to verify the amazing matrix conjecture in general, we can use the algorithm to test for specific values of $n$. As an example, the algorithm has been run on amazing matrices of size less than or equal to six and shows that in arbitrary base $b$  all such matrices are totally nonnegative.

§ DEFINITIONS AND BASIC RESULTS

A matrix with real number entries is said to be totally nonnegative if each of its minors is nonnegative. Totally nonnegative matrices arise in many different settings, for example, oscillations in mechanical
systems, stochastic processes and approximation theory, Pólya frequency sequences,
representation theory, planar networks, ... . Two recent books which serve as useful references for properties of totally nonnegative matrices are [3] and [10]. (The reader should be aware that, in [10], Pinkus uses the term totally positive where we use the term totally nonnegative.)

If $M$ is a matrix and $I$ and $J$ are sets of row and column indices then we will denote by $M(I,J)$ the submatrix of $M$ formed by using rows $I$ and $J$. Also, if $I$ and $J$ have the same size then we set the minor $[I\mid J]_M$ to be the determinant of $M(I,J)$. If it is obvious which matrix is being discussed, then we may drop the subscript $M$ and simply write $[I\mid J]$.

Let $w_0$ be the longest element of the permutation group $S_n$; so that $w_0(i)=n+1-i$, for each $1\leq i\leq n$. An $n\times n$ matrix $M=(m_{ij})$ is cross-symmetric (or centro-symmetric in some sources) if $m_{w_0(i),w_0(j)}=m_{ij}$, for all $1\leq i,j\leq n$. Basic properties of cross-symmetric matrices are discussed in [11].

Define $\tau(M)$ to be the matrix whose $(i,j)$ entry is given by $m_{w_0(i),w_0(j)}$. Note that $M$ is cross-symmetric if and only if $\tau(M)=M$.

Let $J$ be the $n\times n$ matrix whose entries in positions $(i,n+1-i)$ are all equal to $1$, while all other entries are $0$; that is, $J$ has $1$ in each position on the anti-diagonal and is zero elsewhere. It is easy to check that $\tau(M) = JMJ$. Thus, $M$ is cross-symmetric if and only if $M=JMJ$. It follows easily that
$\tau(AB)=\tau(A)\tau(B)$ and that $AB$ is cross-symmetric whenever each of $A$ and $B$ is cross-symmetric.

First, we want to consider the minors of the matrix $\tau(A)$ in terms of the minors of $A$.

Let $I$ and $J$ be index sets of the same size. Then

\[
[I\mid J]_{\tau(A)}=[w_0(I)\mid w_0(J)]_A.
\]

When $|I|=|J|=1$ this is the definition of $\tau(A)$. The proof is then by induction on $|I|$ using induction and Laplace expansions.

The matrix $A$ is totally nonnegative if and only if $\tau(A)$ is totally nonnegative.

Let $A$ be a totally nonnegative matrix. Suppose that there is a pair $(s,t)$ such that $a_{sj}=0$ for $j\leq t$, but $a_{s+1,t}\neq 0$. Then $a_{sj}=0$ for all $j.$

Let $j>t$. It  is enough to show that $a_{sj}=0$.  As $A$ is totally nonnegative,

\[
0\leq [s,s+1\mid t,j] = a_{st}a_{s+1,j}-a_{s+1,t}a_{sj}=0-a_{s+1,t}a_{sj}\leq 0,
\]

so that $a_{s+1,t}a_{sj}=0$
It follows that $a_{sj}=0$, as $a_{s+1,t}>0$.

Let $A$ be an invertible, totally nonnegative matrix. Then there is no pair $(s,t)$ such that $a_{sj}=0$ for $j\leq t$, but $a_{s+1,t}\neq 0$.

If $A$ had such a pair $(s,t)$ then the previous lemma would imply that row $s$ of $A$ is zero, which is impossible for an invertible matrix.

The following result is a special case of <cit.>

The diagonal elements of an invertible, totally nonnegative matrix are all greater than zero.

§ CROSS-SYMMETRIC ELIMINATION

First, we give an informal description of the elimination process that we will use. We start with an invertible, cross-symmetric, totally nonnegative matrix. The aim is to use a version of the Neville elimination procedure to produce a final matrix that is a diagonal matrix. We proceed as with Neville elimination: if we are clearing the lower entries in a given column and want to perform a row operation to replace the last nonzero entry in a column by zero, then we perform a row operation by subtracting a suitable multiple of the row immediately above this last position. Note that, if the matrix is totally nonnegative, the entry immediately above this last position will be nonzero: this is guaranteed by Corollary <ref>. Suppose that this operation involves rows $s$ and $s+1$, then in order to preserve cross-symmetry, at the same time we need to subtract a suitable multiple of row $w_0(s)$ from row $w_0(s+1)$. We need to show that total nonnegativity is preserved by such a move. A complication arises when $n$ is even and $s=n/2$ (which happens precisely when $w_0(s)=s+1$),  so we treat this case separately in the next results where we show what happens under such moves.

We denote by $E(i,j)$ the matrix that is zero in all positions except the $(i,j)$ position, where the entry is $1$. An elementary cross-symmetric matrix is a matrix of the form

\[
\]

for some  $c>0$.

The reduction step for our algorithm will consist of pre-multiplying an invertible, cross-symmetric matrix $A$ by a suitable elementary cross-symmetric matrix $F$. It is obvious that such an $F$ is invertible and cross-symmetric and so $FA$ is also invertible and cross-symmetric. It will remain to show that $FA$ is totally nonnegative  provided that $A$ is totally nonegative. When $n\neq 2s$ this is easy to do: $w_0(s+1)=(n+1)-(s+1)=n-s\neq s$ and so $E(s+1,s)E(w_0(s+1),w_0(s))=0$. It follows that $F=\left(I-cE(s+1,s)\right)\left(I-cE(w_0(s+1),w_0(s))\right)$. If we write these two factors as $F_1$ and $F_2$, we see that $FA=F_1F_2A$, and we can control total nonegativity by proceeding in two stages: first premultiply by $F_2$ and then multiply by $F_1$ and use <cit.> twice; precise details are given below.

<cit.> is essentially due to Whitney [12], see <cit.>.

In order to deal with the first of these products, we need the following preparatory lemma.

Suppose that $n\neq 2s$ and that $A$ is a cross-symmetric,  totally nonnegative $n\times n$ matrix with $a_{st}\neq 0$, while $a_{ij}=0$ whenever $i\geq s$ and $j<t$. Suppose that $a_{s+1,t}\neq 0$ while $a_{s+w,t}=0$ for all $w>1$. Set

\[
\]

(i) $B=(b_{ij}):=FA$ is totally nonnegative, and
(ii)  $b_{st}=a_{st}\neq 0$, while $b_{ij}=0$ for $i\geq s$ and $j<t$. Also, $b_{s+1,t}=a_{s+1,t}\neq 0$ while $b_{s+w,t}=0$ for all $w>1$.

(i) As $\tau(F)= I-a_{s+1,t}a_{st}^{-1}E(s+1,s)$ the pair of matrices $\tau(F)$ and $A$ satisfy the conditions necessary to apply  <cit.> and from that to conclude that $\tau(FA)=\tau(F)\tau(A)$ is totally nonnegative.
It follows that $\tau(B)=\tau(FA)=\tau(F)\tau(A)=\tau(F)A$ is totally nonnegative. As a result, $B$ is totally nonnegative, by Corollary <ref>.

(ii) Note that $n\neq 2s$ implies that $w_0(s+1)= n+1-(s+1)=n-s\neq s$. The matrices $FA$ and $A$ are identical in all rows except row $w_0(s+1)$. Hence, if  $w_0(s+1)<s$ then rows $s+i$ with $i\geq 0$ are the same in $FA$ and $A$ and so the claims in statement (ii) of the lemma follow.

Now, suppose that $w_0(s+1)>s$. The rows other than row $w_0(s+1)$ are the same for $B$ and $A$, so we only have to check the claims in statement (ii) for the relevant entries of $B$ on row $w_0(s+1)$, where, to obtain the value of $b_{w_0(s+1),j}$ we subtract from $a_{w_0(s+1),j}$ a multiple of $a_{w_0(s),j}$.
However, $w_0(s)>w_0(s+1)>s+1$, and so $w_0(s)\geq s+2$. It follows that $a_{w_0(s),j}=0$ for $j\leq t$, and again we conclude that the claims in statement (ii) of the lemma follow.

In order to deal with the case where $n=2s$, we need another preparatory lemma.

Suppose that $n=2s$ and that $A$ is an invertible,  cross-symmetric, totally nonnegative $n\times n$ matrix with $a_{st}\neq 0$, while $a_{ij}=0$ whenever $i\geq s$ and $j<t$. Suppose that $a_{s+1,t}\neq 0$ while $a_{s+w,t}=0$ for all $w>1$. Then $t\leq s$, $t<w_0(t)$ and $a_{s+1,t}<a_{st}$

In this case, $w_0(s)=n+1-s=s+1$ and $w_0(s+1)=s$.
Suppose that  $t>s$ then the hypotheses show that $a_{ss}=0$, which contradicts Lemma <ref>. It follows that $t\leq s$, and that  $t\leq s<s+1=w_0(s)\leq w_0(t)$.

As $A$ is cross-symmetric, $a_{s+1,w_0(t)}=a_{w_0(s),w_0(t)}=a_{st}$ and $a_{s,w_0(t)}=a_{w_0(s+1)w_0(t)}=a_{s+1,t}$. Hence, as $A$ is totally nonnegative,

\[
0\leq[s,s+1\mid t,w_0(t)] = a_{st}a_{s+1,w_0(t)}-a_{s,w_0(t)}a_{s+1,t} = a_{st}^2-a_{s+1,t}^2\,,
\]

so that $a_{s+1,t}\leq a_{st}$.

Suppose that $a_{s+1,t}=a_{st}$. As $A$ is cross-symmetric,  $a_{w_0(s+1),w_0(t)}=a_{w_0(s),w_0(t)}$; that is,
First, suppose that $w_0(t)=t+1$. Then rows $s$ and $s+1$ are equal, since they both take the form $0,\dots,0,a_{st},a_{s,t},0,\dots,0$. This cannot happen, as $A$ is invertible. If $w_0(t)>t+1$, then consider any $j$ such that $t<j<w_0(t)$. We know that $0\leq[s,s+1\mid t,j]=a_{st}a_{s+1,j}-a_{sj}a_{s+1,t}=
a_{st}a_{s+1,j}-a_{sj}a_{s,t}$. As $a_{st}>0$, this implies that $a_{s+1,j}\geq a_{sj}$. A  similar argument with
$[s,s+1\mid j,w_0(t)]$ shows that $a_{sj}\geq a_{s+1,j}$, and so $a_{sj}=a_{s+1,j}$. Again, we see that rows $s$ and $s+1$ are equal, a contradiction; so that $a_{s+1,t}<a_{st}$, as required.

Suppose that  $A=(a_{ij})$ is an $n\times n$ invertible, cross-symmetric, totally nonnegative matrix with $a_{st}\neq 0$ and $a_{ij}=0$ whenever $i\geq s$ and $j<t$. Suppose also that $a_{s+1,t}\neq 0$ while $a_{s+w,t}=0$ for all $w>1$. Set

\[
\]

and set $B=(b_{ij}):=FA$. Then $B$ is an invertible, cross-symmetric, totally nonnegative matrix.

Further, $b_{st}\neq 0$, and $b_{ij}=0$ for $i\geq s$ and $j<t$, while $b_{s+w,t}=0$ for all $w\geq 1$.

As $F$ is invertible and cross-symmetric, we know that $B=FA$ is invertible and cross-symmetric, so we need to show that $B$ is totally nonnegative.

First, suppose that $n\neq 2s$ so that

\[
\left(I-a_{w_0(s+1),w_0(t)}a_{w_0(s)w_0(t)}^{-1}E(w_0(s+1),w_0(s))\right)
\]

Lemma <ref> shows that $B':=(I-a_{w_0(s+1),w_0(t)}a_{w_0(s)w_0(t)}^{-1}E(w_0(s+1),w_0(s))A$ is totally nonnegative, and the entries of $B'$ satisfy the same conditions as those for $A$ that are given in the hypotheses of the proposition, and, in particular, $b'_{st}=a_{st}$ and $b'_{s+1,t}=a_{s+1,t}$.

Hence, $FA=(I-a_{s+1,t}a_{st}^{-1}E(s+1,s))B'$  is totally nonnegative by
<cit.>. Also, $b_{st}=b'_{st}=a_{st}\neq 0$ while $b_{s+1,t}=a_{s+1,t}- a_{s+1,t}a_{st}^{-1}a_{st}=0$.

Now, assume that $n= 2s$.

The matrices $A$ and $B$ differ only in rows $s,s+1$, so we need to know the entries in these rows of $B$:

\[
b_{sj} = a_{sj}-a_{s,w_0(t)}a_{s+1,w_0(t)}^{-1}a_{s+1,j}
\quad{\rm and}\quad
\]

Let $I$ and $J$ be row and column index sets of the same size. We need to show that $[I\mid J]_B\geq 0$. In order to do this, we consider four cases depending on which of $s,s+1$ is/are in $I$.

First, suppose that $s,s+1\not\in I$.  Then $B(I,J)=A(I,J)$ and so $[I\mid J]_B=[I\mid J]_A\geq 0$, as $A$ is totally nonnegative.

Secondly, suppose  that $s\not\in I$ but $s+1\in I$. Set $C:=(I-a_{s+1,t}a_{st}^{-1}E(s+1,s))A$. Then $B(I,J)=C(I,J)$. However, $C(I,J)$ is totally nonnegative, by <cit.>; and so $[I\mid J]_B=[I\mid J]_C\geq 0$.

Next, suppose that $s\in I$, but $s+1\not\in I$. In this case, set

\[
C:= (I-a_{w_0(s+1),w_0(t)}a_{w_0(s)w_0(t)}^{-1}E(w_0(s+1),w_0(s))A.
\]
Then $C$ is totally nonnegative, by
Lemma <ref>. As $B(I,J)=C(I,J)$ we conclude that $[I\mid J]_B\geq 0$.

Finally, suppose that $s,s+1\in I$.

Let $A_1$ be the matrix obtained by replacing row $s$ of $A$ by row $s+1$ of A; let $A_2$ be the matrix obtained by replacing row $s+1$ of $A$ by row $s$ of A; and let $A_3$ be the matrix obtained from $A$ by swopping rows $s$ and $s+1$.

Then, using the fact that the determinant is linear in each row (in particular, in rows $s$ and $s+1$), we obtain

\begin{align*}
[I\mid J]_B= [I\mid J]_{FA} &=[I\mid J]_A - a_{st}a_{s+1,t}^{-1}[I\mid J]_{A_1}
\\
&~~~ - a_{s+1,t}a_{st}^{-1}[I\mid J]_{A_2}
+ a_{st}a_{s+1,t}^{-1}a_{s+1,t}a_{st}^{-1}[I\mid J]_{A_3}
\end{align*}

Now, $[I\mid J]_{A_1}=[I\mid J]_{A_2}=0$, as
$A_1$ and $A_2$ have repeated rows that are included in the row set $I$. Also, $[I\mid J]_{A_3}=-[I\mid J]_A$ as $A_3$ is obtained from $A$ by swopping two adjacent rows.

\begin{align*}
[I\mid J]_B
[I\mid J]_A-a_{s,w_0(t)}a_{s+1,w_0(t)}^{-1}a_{s+1,t}a_{st}^{-1}[I\mid J]_A\\
&=a_{s+1,w_0(t)}^{-1}a_{st}^{-1}\left( a_{st}a_{s+1,w_0(t)} - a_{s,w_0(t)}a_{s+1,t} \right)[I\mid J]_A
\end{align*}

As $A$ is totally nonnegative, $[I\mid J]_A\geq 0$. Also, $a_{s+1,w_0(t)}=a_{st}>0$ from the hypotheses and the  fact that $A$ is cross-symmetric.
Recalling that $t<w_0(t)$, we obtain

\[
a_{st}a_{s+1,w_0(t)} - a_{s,w_0(t)}a_{s+1,t} = [s,s+1\mid t,w_0(t)]_A\geq 0
\]

and it follows that
$[I\mid J]_B\geq 0$.

Finally, note that

\begin{align*}
b_{st}&=a_{st} - a_{s,w_0(t)}a_{s+1,w_0(t)}^{-1}a_{s+1,t}=a_{st} - a_{w_0(s+1),w_0(t)}a_{w_0(s),w_0(t)}^{-1}a_{s+1,t}\\
&= a_{st} - a_{s+1,t}a_{s,t}^{-1}a_{s+1,t}=\left(a_{st}^2-a_{s+1,t}^2\right)a_{st}^{-1} >0,
\end{align*}

where the inequality occurs because we know that $a_{st}>a_{s+1,t}$, by Lemma <ref>.
The other claims for the elements of $B$ follow easily.

Let $A$ be an $n\times n$ invertible, cross-symmetric, totally nonnegative matrix. Then there
is a sequence of elementary cross-symmetric matrices $F_1,\dots,F_d$ such that
$F_d\dots F_1A=D$ where $D=(d_{ij})$ is a cross-symmetric, diagonal matrix with $d_{ii}>0$ for $1\leq i\leq n$.

We put the positions of the matrix below the diagonal in the order

\[
(n,1), \dots, (2,1), (n,2),\dots,(3,2), \dots,(n,n-1);
\]

that is, we move from the bottom of the first column upwards, then up the second column, etc. Use the previous result to set each of these elements to zero. As we do this, the cross-symmetry property ensures that the above diagonal elements also become zero. At the end, we reach a diagonal matrix which is totally nonnegative and, in fact, must have strictly positive entries, as it is invertible.

In the setting of this theorem, we see that $A=F_1^{-1}\dots F_d^{-1} D$. We now identify the form of these inverses.

A (cross-symmetric, totally nonnegative) atom is a matrix $F$ that takes one of the following two forms. Either $n\neq 2s$ and
$F:=I+cE(s+1,s)+cE(w_0(s+1),w_0(s))$ for some $c>0$, or, $n=2s$ and $F=(f_{ij})$ where $f_{ss}=f_{s+1,s+1}=1/(1-c^2), f_{s,s+1}=f_{s+1,s} =c/(1-c^2)$ with $0<c<1$, while the other diagonal elements are all equal to $1$ and the other off-diagonal elements are all equal to $0$.  (Note that these matrices $F$ are indeed cross-symmetric and totally nonnegative.)

(i) Suppose that $n\neq 2s$ and that  $F=I-cE(s+1,s)-cE(w_0(s+1),w_0(s))$ for some $c>0$. Then
$F^{-1} =I+cE(s+1,s)+cE(w_0(s+1),w_0(s))$ is a cross-symmetric, totally nonnegative atom of the first kind defined above.

(ii) Suppose that $n= 2s$ and that  $F=I-cE(s+1,s)-cE(w_0(s+1),w_0(s))$ for some $0<c<1$. Then $F^{-1}$ is a cross-symmetric, totally nonnegative atom of the second type defined above.

(i) This is just a matter of checking that

\[
\]

(ii) The $2\times 2$ submatrix of $F$ formed from rows $s,s+1$ and columns $s,s+1$ has the form
\end{smallmatrix}\right)$. The inverse of this matrix is

\[
\begin{pmatrix}
\frac{1}{1-c^2}&\frac{c}{1-c^2}\\
\frac{c}{1-c^2}&\frac{1}{1-c^2},
\end{pmatrix}.
\]

Hence,  $F^{-1}$ is easily seen to be a cross-symmetric totally nonnegative atom of the second kind defined above.

Let $A$ be an $n\times n$ invertible, cross-symmetric, totally nonnegative matrix. Then there is a factorisation of $A$ as a product of cross-symmetric totally, nonnegative atoms and a cross-symmetric diagonal matrix with strictly positive diagonal entries.

Conversely, any product $A_1\dots A_t D$ of cross-symmetric, totally nonnegative atoms $A_i$ and a cross-symmetric  diagonal matrix $D$ with strictly positive diagonal entries is an invertible,  cross-symmetric, totally nonnegative matrix.

In the setting of the theorem above, we have $A=F_1^{-1}\dots F_d^{-1} D$, and the inverses that occur are cross-symmetric totally nonnegative atoms by the previous lemma. The converse statement is immediate from earlier comments.

§ THE ALGORITHM

The results of the previous section provide us with an algorithmic way of testing when an invertible, cross-symmetric $n\times n$ matrix $A$ is totally nonnegative. Informally, the algorithm proceeds as follows.

We list the  positions  of a matrix below the diagonal in the order $(n,1), (n-1,1), \dots, (2,1),\\(n,2),\dots, (3,2),\dots, (n,n-1)$; that is, we move from the bottom of the first column upwards, then up the second column, etc.

If all of these entries in $A$ are zero then $A$ is a diagonal matrix, so check if all $a_{ii}>0$, in which case the original $A$ is totally nonnegative, otherwise the original $A$ is not totally nonnegative.

If there are nonzero elements, then suppose that the first in the list is $a_{s+1,t}$. If $a_{st}\leq 0$ then $A$ is not totally nonnegative. If $a_{st}>0$ then replace $A$ by $FA$ where

\[
\]

and repeat the above instructions with the new $A$.

If we keep track of the $F$ that arise then calculate each $F^{-1}$, we recover the factorisation given by Corollary <ref>.

§ APPLICATIONS TO HOLTE'S AMAZING MATRIX

There is a very close connection between totally nonegative matrices and weighted path matrices of directed planar networks.  In fact, theorems of Lindström [8] and Brenti <cit.> show that a real matrix $A$ is totally nonnegative if and only if $A$ is the weighted path matrix of a weighted planar network.  A good introduction to these ideas is given in

In this section, we illustrate the results of the earlier sections by considering Holte's “Amazing Matrix” and show that various cases are indeed totally nonnegative, as conjectured in [2].

Holte's “Amazing Matrix” is the $n\times n$ matrix $P=(p_{ij})$ with

\[
p_{ij}=\frac{1}{b^n}\sum_{r=0}^{j-\lfloor i/b\rfloor}(-1)^r \binom{n+1}{r}\binom{n-1-i+(j+1-r)b}{n}.
\]

The entry $p_{ij}$ gives the probability that, when adding $n$ random numbers in base $b$, the next carry will be $j$, given that the previous carry was $i$, see [7]. (Note that Holte indexes the rows and columns of an $n\times n$ amazing matrix by $0,1,\dots,n-1$.) Holte shows that $P$ is cross-symmetric <cit.>. It will be convenient for us to use the scaled version $P':=b^nP$ to avoid fractions. As examples of $P'$, when $b=3$ the $2\times 2, 3\times 3$ and $4\times 4$ matrices are displayed below.

\[
\begin{pmatrix}
\end{pmatrix}
\qquad
\begin{pmatrix}
\end{pmatrix}
\qquad
\begin{pmatrix}
\end{pmatrix}
\]

The factorisation of the $2\times 2$ matrix above that is given by the algorithm is:

\[
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix}
\]

and the first factor is an atom of the second kind where $c=1/2$.

The factorisation into atoms of the $n=b=3$ scaled amazing matrix  that is given by the algorithm developed earlier is:

\[
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix},
\]

verifying that the matrix is totally nonnegative, as each of the factors is totally nonnegative.

The above factorisation gives rise to the  planar network in Figure <ref> whose weighted path matrix is the amazing matrix with $n=b=3$ (edges without weights attached are taken to have weight $1$, and all edges are directed from left to right):

\xymatrixrowsep{10ex}\xymatrixcolsep{10ex}\def\objectstyle{\scriptstyle}
\xymatrix@!0{
S_1\edge[r]&\bullet\edge[rr]\edge[dr]_{1/4}&\edge[r]&\bullet\edge[r]\edge[dr]^{5/4}&\bullet\edge[r] ^{9}&T_1\\
S_2\edge[rr]&\edge[r]&\bullet\edge[rr]\edge[ru]^{4/9}\edge[rd]_{4/9}&\edge[r]&\bullet\edge[r] ^{9}&T_2\\
S_3\edge[r]&\bullet\edge[rr]\edge[ru]^{1/4}&\edge[r]&\bullet\edge[r]\edge[ur]_{5/4}&\bullet\edge[r] ^{9}&T_3\\
Weighted planar networks for  scaling of the $3\times 3$ Amazing Matrix with base $b=3$
(all edges directed left to right)

The cross-symmetry property is manifested in the planar network by the symmetry in the horizontal line at the centre of the network.

The factorisation of the scaled amazing matrix in the case where $n=4$ and $b=3$ contains atoms of the second kind and leads to the planar network shown in Figure <ref>. Again, total nonnegativity is verified and the cross-symmetry property is seen by the symmetry about the horizontal line through the middle of the network.

\xymatrixrowsep{10ex}\xymatrixcolsep{10ex}\def\objectstyle{\scriptstyle}
\xymatrix@!0{
Weighted planar network for  scaling of the $4\times 4$ Amazing Matrix with base $b=3$
(all edges directed left to right)

We have run the algorithm in arbitrary base $b$ up to $n=6$ and the total nonnegativity conjecture is verified in each of these cases.

[1] F Brenti, The applications of total positivity to combinatorics, and conversely, In: Gasca,
M., Micchelli, C.A. (eds.) Total Positivity and its Applications. Kluwer, Dordrecht (1996)

[2] P Diaconis and J Fulman, Carries, Shuffling and an Amazing Matrix, Amer. Math. Monthly
116 No. 9 (2009), 788-803

[3] S M Fallat and C R Johnson, Totally Nonnegative Matrices, Princeton Series in Applied Mathematics, Princeton University Press, Princeton 2011

[4] S Fomin and A Zelevinsky, Total Positivity: Tests and Parameterizations, Mathematical Intelligencer 22 (2000), 23-33

[5] K R Goodearl, S Launois and T H Lenagan, Totally nonnegative cells and matrix
Poisson varieties, Advances in Mathematics 226 (2011), 779-826.

[6] K R Goodearl and T H Lenagan, LU decomposition of totally nonnegative matrices, Linear Algebra Appl. 436, 2554-2566 (2012)

[7] J M Holte, Carries, Combinatorics and an Amazing matrix, Amer. Math. Monthly 104 No. 2 (1997), 138-149

[8] B Lindström, On the Vector Representations of Induced Matroids, Bulletin London Math.
Soc. 5 (1973) 85-90

[9] A McMillan, Total positivity of a shuffle matrix, Involve 4:1 (2012), 61-65

[10] A Pinkus, Totally Positive Matrices, Cambridge Tracts in Mathematics 181, Cambridge University Press, Cambridge, 2010

[11] J Weaver, Centrosymmetric (Cross-Symmetric) Matrices, Their Basic Properties, Eigenvalues, and Eigenvectors, Amer. Math. Monthly,  92 No. 10 (1985),  711-717

[12] A M Whitney, A reduction theorem for totally positive matrices, J. Analyse Math. 2 (1952), 88-92

Maxwell Institute,

School of Mathematics,
University of Edinburgh,

James Clerk Maxwell Building,

The King's Buildings,

Peter Guthrie Tait Road,

Edinburgh EH9 3FD