Let A∈Fq×p be a nonzero matrix over a field F, and let f be any monic polynomial of degree n=p+q with coefficients in F. A completion problem proposed and solved by de Oliveira asks for the existence ...of a matrix of order n with characteristic polynomial f and such that its q×p submatrix in the left down corner is equal to A. Let C(f)∈Fn×n be the companion matrix of f. We will construct a matrix XA∈Fn×n (which depends exclusively on A) such that XA−1C(f)XA is a closed form solution of this completion problem.
In this paper we give solutions to Hamburger moment problems with missing entries. The problem of completing partial positive sequences is considered. The main result is a characterization of ...positive definite completable patterns, namely patterns that guarantee the existence of Hamburger moment completion of a partial positive definite sequence. Moreover, several patterns which are not positive definite completable are given.
Let
Λ
=
{
λ
1
,
…
,
λ
n
}
,
n
⩾
2
, be a given multiset of elements in an integral domain
R
and let
P be a matrix of order
n with at most
2
n
-
3
prescribed entries that belong to
R
. Under the ...assumption that each row, each column and the diagonal of
P have at least one unprescribed entry, we prove that
P can be completed over
R
to obtain a matrix
A with spectrum
Λ
. We describe an algorithm to construct
A. This result is an extension to integral domains of a classical completion result by Herskowitz for fields.
We study Semidefinite Programming,
SDP
, relaxations for Sensor Network Localization,
SNL
, with anchors and with noisy distance information. The main point of the paper is to view
SNL
as a (nearest) ...Euclidean Distance Matrix,
EDM
, completion problem that does not distinguish between the anchors and the sensors. We show that there are advantages for using the well studied
EDM
model. In fact, the set of anchors simply corresponds to a given fixed clique for the graph of the
EDM
problem.
We next propose a method of projection when large cliques or dense subgraphs are identified. This projection reduces the size, and improves the stability, of the relaxation. In addition, by viewing the problem as an
EDM
completion problem, we are able to derive a new approximation scheme for the sensors from the
SDP
approximation. This yields, on average, better low rank approximations for the low dimensional realizations. This further emphasizes the theme that
SNL
is in fact just an
EDM
problem.
We solve the
SDP
relaxations using a primal-dual interior/exterior-point algorithm based on the Gauss-Newton search direction. By not restricting iterations to the interior, we usually get lower rank optimal solutions and thus, better approximations for the
SNL
problem. We discuss the relative stability and strength of two formulations and the corresponding algorithms that are used. In particular, we show that the quadratic formulation arising from the
SDP
relaxation is better conditioned than the linearized form that is used in the literature.
Let
R
be an arbitrary integral domain, let
∧
=
{
λ
1
,
…
,
λ
n
}
be a multiset of elements of
R
, let
σ
be a permutation of
{
1
,
…
,
k
}
let
n
1
,
…
,
n
k
be positive integers such that
n
1
+
⋯
+
n
...k
=
n
, and for
r
=
1
,
…
,
k
let
A
r
∈
R
n
r
×
n
σ
(
r
)
. We are interested in the problem of finding a block matrix
Q
=
Q
rs
r
,
s
=
1
k
∈
R
n
×
n
with spectrum
Λ
and such that
Q
r
σ
(
r
)
=
A
r
for
r
=
1
,
…
,
k
. Cravo and Silva completely characterized the existence of such a matrix when
R
is a field. In this work we construct a solution matrix
Q
that solves the problem when
R
is an integral domain with two exceptions: (i)
k
=
2
; (ii)
k
≥
3
,
σ
(
r
)
=
r
and
n
r
>
n
/
2
for some
r
.
What makes this work quite unique in this area is that we consider the problem over the more general algebraic structure of integral domains, which includes the important case of integers. Furthermore, we provide an explicit and easy to implement finite step algorithm that constructs an specific solution matrix (we point out that Cravo and Silva’s proof is not constructive).
In R. Grone, C.R. Johnson, E. Sa, H. Wolkowicz, Positive definite completions of partial Hermitian matrices, Linear Algebra Appl. 58 (1984) 109–124 the positive definite (semi-) completion problem in ...which the underlying graph is chordal was solved. For the positive definite case, the process was constructive and the completion was obtained by completing the partial matrix an entry at a time. For the positive semidefinite case, they obtained completions of a particular sequence of partial positive definite matrices with the same underlying graph and noted that there is a convergent subsequence of these completions that converges to the desired completion. Here, in the chordal case, we provide a constructive solution, based entirely on matrix/graph theoretic methods, to the positive (semi-)definite completion problem. Our solution associates a specific tree (called the “clique tree” C.R. Johnson, M. Lundquist, Matrices with chordal inverse zero-patterns, Linear and Multilinear Algebra 36 (1993) 1–17) with the (chordal) graph of the given partial positive (semi-)definite matrix. This tree structure allows us to complete the matrix a “block at a time” as opposed to an “entry at a time” (as in Grone et al. (1984) for the positive definite case). In Grone et al. (1984), using complex analytic techniques, the completion for the positive definite case was shown to be the unique determinant maximizing completion and was shown to be the unique completion that has zeros in its inverse in the positions corresponding to the unspecified entries of the partial matrix. Here, we show the same using only matrix/graph theoretic tools.
Extending partial tournaments Beasley, LeRoy B.; Brown, David E.; Reid, K. Brooks
Mathematical and computer modelling,
07/2009, Volume:
50, Issue:
1
Journal Article
Peer reviewed
Open access
Let
A
be a
(
0
,
1
,
∗
)
-matrix with main diagonal all 0’s and such that if
a
i
,
j
=
1
or
∗
then
a
j
,
i
=
∗
or 0. Under what conditions on the row sums, and or column sums, of
A
is it possible to ...change the
∗
’s to 0’s or 1’s and obtain a tournament matrix (the adjacency matrix of a tournament) with a specified score sequence? We answer this question in the case of regular and nearly regular tournaments. The result we give is best possible in the sense that no relaxation of any condition will always yield a matrix that can be so extended.
In this paper we completely determine the possible eigenvalues of a matrix of a system obtained as a result of special loop connections of arbitrary many linear systems.
Based on previous theoretical results we present in this paper a global estimation scheme for solving the stable 2D autoregressive filter problem. The different algorithms are based on the ...traditional Newton method and on the log barrier method that is employed in semi-definite programming. The Newton method is the faster one but the barrier method ensures that the iterates stay in the cone of positive semidefinites. In addition, a numerical test for the existence of a stable factorization of a two-variable squared magnitude response function is presented.
PDF
